Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels

Abstract

An algorithm for the detection of overlapping natural communities in networks was proposed by Lancichinetti, Fortunato, and Kertesz (LFK) last year. The LFK algorithm constructs natural communities of (in principle) all nodes of a graph by maximising the local fitness of communities. The resulting modules can overlap. The generation of communities can easily be repeated for many values of resolution; thus allowing different views on the network at different resolutions. We implemented the main idea of the LFK algorithm---to generate natural communities of each node of a network---in a different way. We start with a value of the resolution parameter that is high enough for each node to be its own natural community. As soon as the resolution is reduced, each node acquires other nodes as members of its community, i.e. natural communities grow. For each community found at a certain resolution level we calculate the next lower resolution where a node is added. After adding a node to a community of a seed node we check whether it is also the natural community of a node that we have already analysed. In this case, we can stop expanding the seed node's community. We tested our algorithm on a small benchmark graph and on a network of about 500 papers in information science (weighted with the Salton index of bibliographic coupling). In our tests, this approach results in characteristic ranges of resolution where a large resolution change does not lead to a growth of the natural community. Such stable modules were also obtained by applying the LFK algorithm but since we determine communities for all resolution values in one run, our approach is faster than the LFK reference. And our algorithm reveals the hierarchical structure of the graph more easily.

10 pages, 12 figures, also presented as "A local algorithm to get overlapping communities at all resolution levels in one run" in a poster session at ASONAM conference, Odense, Denmark, August 2010

References in corpus (5)

• Cooperative Game Theory Approaches for Network Partitioning
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Detecting highly overlapping community structure by greedy clique expansion
• Line Graphs of Weighted Networks for Overlapping Communities

Cited by in corpus (6)

• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Evaluating Overlapping Communities with the Conductance of their Boundary Nodes
• Partitioning Breaks Communities
• Estimating Thematic Similarity of Scholarly Papers with Their Resistance Distance in an Electric Network Model