Overlapping community detection using a community optimized graph swarm

Detection of communities within social networks is a nontrivial problem. Allowing communities to overlap—i.e. nodes can belong to more than one community simultaneously—further complicates the problem. Nevertheless, people do belong to multiple social groups simultaneously and being able to detect overlapping communities is an important step into being able to understand and analyze social networks. A common practice in community detection (clustering) is to view the network (graph) as a whole and have a central control process determine how nodes are clustered. That central control, we believe, is a limitation to performance. In our previous work, we showed that the individual’s view of his or hers social groups could be aggregated to produce communities. In this paper, we propose a unique approach to community detection that combines the individual’s view of a community, not having the view the graph as a whole, with swarm intelligence as a means of removing the central control mechanism. Our approach offers a community detection solution that finds overlapping communities while running in O(n log ² n) time.