Abstract
Community detection has received a great deal of attention, since it could help to reveal the useful information hidden in complex networks. Although most previous modularity-based and local modularity-based community detection algorithms could detect strong communities, they may fail to exactly detect several weak communities. In this work, we define a network with clear or ambiguous community structures based on the types of its communities. A seed-expanding method based on random walks is proposed to detect communities for networks, especially for the networks with ambiguous community structures. We identify local maximum degree nodes, and detect seed communities in a network. Then, the probability of a node belonging to each community is calculated based on the total probability model and random walks, and each community is expanded by repeatedly adding the node which is most likely to belong to it. Finally, we use the community optimization method to ensure that each node is in a community. Experimental results on both computer-generated and real-world networks demonstrate that the quality of the communities detected by the proposed algorithm is superior to the- state-of-the-art algorithms in the networks with ambiguous community structures.
Introduction
In network science, community detection is the process of grouping nodes that are more densely connected to each other than to the rest of the network. However, not all communities are created equal. Researchers distinguish between strong communities (where every node has more internal than external connections) and weak communities (where the sum of internal degrees is merely greater than the sum of external degrees).
Most popular algorithms, such as the Louvain method (FUA) or Girvan-Newman (GN), rely on "modularity maximization." These methods often suffer from a "resolution limit," meaning they fail to detect small or weak communities, particularly in "ambiguous" networks where the structure is not crystal clear. This paper proposes the Random Walk Algorithm (RWA), a method designed to remain robust even when community boundaries are fuzzy.
Methodology
The proposed RWA algorithm follows a three-step pipeline:
- Detecting Seed Communities: To avoid the instability of starting with a single random node, RWA identifies "local maximum degree nodes"—hubs with a higher degree than all their neighbors. It then forms a small, dense 3-node subgraph around these hubs to serve as a stable "seed."
- Expansion via Random Walks: The algorithm expands these seeds by calculating the probability that a random walker starting at an unassigned node would "teleport" into a specific community. This uses a total probability model to account for structural similarity.
- Community Optimization: To ensure every node is accounted for, a "tightness" measure assigns low-degree outlier nodes. Additionally, if two expanded communities share more than 50% of their nodes, they are merged to refine the final structure.
Experimental Evaluation
The authors evaluated RWA against five state-of-the-art algorithms (GN, FN, FUA, FEC, and LMDR) using both synthetic benchmarks (GN and LFR) and real-world networks, including Zachary’s Karate Club and the American College Football network.
As illustrated in the figure above, RWA (represented by red squares) significantly outperforms its competitors in the "ambiguous" range of the GN benchmark, specifically where the internal edge probability ($P_{in}$) falls between 0.4 and 0.6. While most algorithms perform similarly when communities are clear ($P_{in} \ge 0.8$), RWA maintains high Normalized Mutual Information (NMI) and F1-scores as the structure becomes noisier. In real-world datasets, RWA correctly identified 77.78% of all weak communities, whereas the next best algorithms (FUA/FEC) only managed 22.22%.
Discussion and Conclusion
The success of RWA lies in its stability and its ability to handle ambiguity. By using dense subgraphs as seeds rather than arbitrary nodes, the algorithm avoids the sensitivity issues found in previous random-walk methods. Furthermore, because random walks calculate membership as a probability rather than a hard greedy choice, they are naturally suited for navigating the "fuzzy" connections that modularity-based methods overlook.
While highly effective for ambiguous structures, future work is needed to scale the algorithm for "big data" networks containing millions of nodes and to adapt it for detecting overlapping communities where nodes belong to multiple groups simultaneously.
Summary updated