PHD, Kent State University, 2012, College of Arts and Sciences / Department of Computer Science
With the rise of the internet, mobile communications, electronic transactions, and personal broadcasting, the scale of connectedness has grown immensely. Not only can an individual interact with thousands and millions of others, but details about those interactions are being stored in databases, for later retrieval and analysis. Two key concepts help us to simplify and understand networks: structural patterns and social role. Networks often exhibit recurring structural patterns, and similar structure often correlates to similar functional or behavioral role. The presence of recurring roles and structural patterns also enables transfer learning: what we know about one network can be used to help us understand or identify information in another network.
While the theoretical concept of structural roles is well-established, however, there is no agreed-upon real-valued measure of role similarity. In this work, we focus on two specific computational problems: (1) developing a well-principled and scalable measure for node structural similarity, and (2) finding the optimal node-to-node alignment between two graphs.
This dissertation makes the following contributions. First, to establish a sound theoretical basis, we present an axiomatic definition of a role similarity measure. This proves a clear and uniform understanding for the characteristics needed by any role similarity. The key axiom is automorphism/isomorphism confirmation: if two nodes are automorphically equivalent, then an admissible similarity measure must positively confirm this fact.
Second, we present RoleSim, a role similarity metric which satisfies these axioms and which can be computed with a simple iterative algorithm. RoleSim is founded on the concept of maximal matching of neighbor similarity.
We rigorously prove that RoleSim satisfies all the axiomatic properties and demonstrate its superior interpretive power of RoleSim both synthetic and real datasets.
Third, we establish a recursive connection betw (open full item for complete abstract)
Committee: Ruoming Jin (Advisor)
Subjects: Computer Science