Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2024 Feb 26;14(1):4694.
doi: 10.1038/s41598-024-55190-7.

Community detection with Greedy Modularity disassembly strategy

Heru Cahya Rustamaji  1   2 , Wisnu Ananta Kusuma  3   4 , Sri Nurdiati  5 , Irmanida Batubara  6   7
Affiliations

Community detection with Greedy Modularity disassembly strategy

Heru Cahya Rustamaji et al. Sci Rep. .

Abstract

Community detection recognizes groups of densely connected nodes across networks, one of the fundamental procedures in network analysis. This research boosts the standard but locally optimized Greedy Modularity algorithm for community detection. We introduce innovative exploration techniques that include a variety of node and community disassembly strategies. These strategies include methods like non-triad creating, feeble, random as well as inadequate embeddedness for nodes, as well as low internal edge density, low triad participation ratio, weak, low conductance as well as random tactics for communities. We present a methodology that showcases the improvement in modularity across the wide variety of real-world and synthetic networks over the standard approaches. A detailed comparison against other well-known community detection algorithms further illustrates the better performance of our improved method. This study not only optimizes the process of community detection but also broadens the scope for a more nuanced and effective network analysis that may pave the way for more insights as to the dynamism and structures of its functioning by effectively addressing and overcoming the limitations that are inherently attached with the existing community detection algorithms.

Keywords: Community detection; Disassembly greedy; Greedy Modularity.

PubMed Disclaimer

Conflict of interest statement

The authors declare no competing interests.

Figures

Figure 1
Figure 1
Node exploration, node disassembly (a) Two communities are formed, blue and red (b) Node 0 is removed from the blue community (c) Node 0 joins the red community.
Figure 2
Figure 2
Community exploration, community disassembly (a) two communities are formed, blue and red (b) the blue community is disassembled, and each node becomes a community.
Algorithm 1
Algorithm 1
The algorithm disassembly random nodes.
Algorithm 2
Algorithm 2
Weak node disassembly algorithm on weak community.
Algorithm 3
Algorithm 3
The algorithm disassembly nodes with low embeddedness.
Algorithm 4
Algorithm 4
The algorithm disassembly nodes that don’t form a triad.
Algorithm 5
Algorithm 5
Random community disassembly algorithm.
Algorithm 6
Algorithm 6
Weak community disassembly algorithm.
Algorithm 7
Algorithm 7
The algorithm disassembly the community with low internal edge density.
Algorithm 8
Algorithm 8
The algorithm disassembly the community with a low triad participation ratio.
Algorithm 9
Algorithm 9
The algorithm disassemble the community with high conductance.
Figure 3
Figure 3
The value of the modularity of the DGM algorithm on the Zachary dataset (n=34), c=30.
Figure 4
Figure 4
Visualization of community detection on (a) Zachary faction ground truth (b) Greedy Modularity (c) DGM.
Figure 5
Figure 5
NMI and F1 Score visualization with heatmap.
Figure 6
Figure 6
Visualisasi.
See this image and copyright information in PMC

References

    1. Barabási A-L. Network Science. Cambridge University Press; 2016.
    1. Shang KK, Small M, Wang Y, Yin D, Li S. A novel metric for community detection. Europhys. Lett. 2020;129:68002. doi: 10.1209/0295-5075/129/68002. - DOI
    1. Chakraborty T, Dalmia A, Mukherjee A, Ganguly N. Metrics for community analysis: A survey. ACM Comput. Surv. 2017;50:1–37. doi: 10.1145/3091106. - DOI
    1. Chen M, Kuzmin K, Szymanski BK. Community detection via maximization of modularity and its variants. IEEE Trans. Comput. Soc. Syst. 2014;1:46–65. doi: 10.1109/TCSS.2014.2307458. - DOI
    1. Zhu J, et al. A no self-edge stochastic block model and a heuristic algorithm for balanced anti-community detection in networks. Inf. Sci. 2020;518:95–112. doi: 10.1016/j.ins.2020.01.005. - DOI