Community-affinity: Measuring strength of memberships of nodes in network communities.

摘要

Detecting community structure in networks has been a widely studied area. While most of the methods produce an exclusive membership of the nodes, the nodes in real-world networks tend to partially belong to more than one community. In this thesis, we study some methods that have been used to quantify the strength of memberships of nodes in different communities (or community-affinity, as we call it) and also define three of our own methods. Our first method is based on personalized PageRanks of the nodes, the second is based on the individual contribution of nodes to the modularity of the graph, and the last is based on the common neighborhood between two nodes. We first discuss different notions of community-affinity, each of which is followed by formulations that capture that notion. We then discuss the concept of stability, which uses community-affinity scores of the nodes to compute how "stable" each node is in a given community structure and how we can use this information in estimating the quality of a given community structure. Towards the end, we introduce a community detection algorithm, which "peels" communities one by one from a graph. The results of our experiments show that our algorithm is very accurate even for a large number of nodes in a graph. Our algorithm is fast and it performs very well on real-world graphs compared to the state of the art algorithms.