University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Monday, May 14, 2012

DTC Seminar Series

Circles of trust: An axiomatic construction of clustering in asymmetric networks


Alejandro Ribeiro
University of Pennsylvania

Monday, May 14, 2012
4:00 pm

402 Walter Library

 Alejandro RibeiroWe present an axiomatic construction of hierarchical clustering in asymmetric networks where the dissimilarity from node a to node b is not necessarily equal to the dissimilarity from node b to node a. The theory is built on the axioms of value, influence, and transformation. The Axiom of Value says that in a two-node network the nodes cluster at resolution equal to the maximum dissimilarity between them. The Axiom of Influence says that no clusters are formed at resolutions that do not allow bidirectional paths to be formed. The Axiom of Transformation states that if we consider a network and reduce all pairwise dissimilarities, the level at which two nodes become part of the same cluster is not larger than the level at which they were clustered together in the original network. Two asymmetric hierarchical clustering methods that abide to these axioms are derived. Reciprocal clustering requires clusters to form through arcs that are similar in both directions. Nonreciprocal clustering allows clusters to form through cycles of small dissimilarity. We further show that any clustering method that satisfies the axioms of value, influence, and transformation lies between reciprocal and nonreciprocal clustering in the sense that all other methods cluster two points together at resolutions larger than nonreciprocal clustering and smaller than reciprocal clustering. We apply this theory to the formation of circles of trust in social networks. Nodes that do not cluster together with nonreciprocal clustering cannot be part of a circle of trust. Nodes that cluster together with reciprocal clustering are definitely part of a circle of trust. In between, the answer depends on the extent to which reciprocal trust propagation is required or nonreciprocal trust propagation is acceptable.


Alejandro Ribeiro is an assistant professor at the Department of Electrical and Systems Engineering at the University of Pennsylvania, Philadelphia, where he started in 2008. He received the B.Sc. in electrical engineering from the Universidad de la Republica Oriental del Uruguay, Montevideo, in 1998. From 2003 to 2008 he was at the Department of Electrical and Computer Engineering, the University of Minnesota, Minneapolis, where he received the M.Sc. and Ph.D. in electrical engineering. From 1998 to 2003 he was a member of the technical staff at Bellsouth Montevideo. His research interests lie in the areas of communication, signal processing, and networking. His current research focuses on wireless communications and networking, distributed signal processing, wireless sensor networks, and communications for mobile robots. He received the 2012 S. Reid Warren, Jr. Award presented by Penn's undergraduate student body for outstanding teaching and the NSF CAREER award in 2010. He is also a Fulbright scholar and the recipient of student paper awards at ICASSP 2005 and ICASSP 2006.