Robustness of community structure to node removal

DOI10.1088/1742-5468/2015/03/P03003MaRDI QIDQ3302204zbMATH OpenFDO

Authors Diego R. Amancio, Osvaldo N. jun. Oliveira, Luciano Da Fontoura Costa

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.6295

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Statistical sampling theory and related topics (62D99)

Abstract: The identification of modular structures is essential for characterizing real networks formed by a mesoscopic level of organization where clusters contain nodes with a high internal degree of connectivity. Many methods have been developed to unveil community structures, but only a few studies have probed their suitability in incomplete networks. Here we assess the accuracy of community detection techniques in incomplete networks generated in sampling processes. We show that the walktrap and fast greedy algorithms are highly accurate for detecting the modular structure of incomplete complex networks even if many of their nodes are removed. Furthermore, we implemented an approach that improved the time performance of the walktrap and fast greedy algorithms, while retaining the accuracy rate in identifying the community membership of nodes. Taken together our results show that this new approach can be applied to speed up virtually any community detection method in dense complex networks, as it is the case of similarity networks.

Recommendations

• Fast unfolding of communities in large networks
• Finding network communities using modularity density
• Validation of community robustness
• Detecting network communities: a new systematic and efficient algorithm
• Computing Communities in Large Networks Using Random Walks

Cites work

• Community structure in social and biological networks
• Computing Communities in Large Networks Using Random Walks
• Markov Chains
• Random walks on lattices. II
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Traffic flow: A statistical physics point of view

Cited in

(4)

• Mitigation of attacks and errors on community structure in complex networks
• High-performance community detection in social networks using a deep transitive autoencoder
• An online expectation maximization algorithm for exploring general structure in massive networks
• Validation of community robustness

This page was built for publication: Robustness of community structure to node removal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302204)