CIF: SMALL: Circles of Trust: An Axiomatic Construction of Clustering in Asymmetric Networks

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

This project develops an axiomatic theory of hierarchical clustering for asymmetric networks as is typical of trust propagation. Say, for example, that Miranda trusts Billy who trusts Ariel who trusts Miranda, but there has not been enough interactions in the opposite direction to establish trust. When these three people meet, shall they trust each other? The answer to this question is equivalent to the determination of whether Miranda, Billy, and Ariel are part of the same cluster: their circle of trust. The axioms of value, influence, and transformation are postulated. 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. Generic properties of any method that satisfies these axioms are explored and specific methods that abide by these axioms are derived. To enrich the axiomatic exploration of asymmetric clustering an application thrust and three theory thrusts are pursued. The application thrust explores the formation of circles of trust in social networks and the design of protocols to establish trust in technological networks. The theory thrusts will study alternative axiomatic formulations, stability of asymmetric hierarchical clustering algorithms, and the determination of algorithms to compute hierarchical clusters. The educational agenda is integrated into the Market and Social Systems Engineering (MKSE) program at the University of Pennsylvania. The MKSE program is an undergraduate course of study that fully integrates the disciplines needed to design and analyze the complex networks that are reshaping our society. Given the importance of trust in these networks the research undertaken in the context of this project is incorporated into classes in the MKSE program. The excitement an idea like the formalization of trust propagation generates is further exploited to draw attention to the MKSE and Systems Engineering programs from the wider academic community. These ideas are part of a long term effort on the part of the PI to contribute to the closing of the excitement, challenge, and discipline gaps.