Group detection in complex networks: an algorithm and comparison of the state of the art

DOI10.1016/J.PHYSA.2013.12.003MaRDI QIDQ1782604zbMATH OpenOpenAlexFDO

Authors Lovro Šubelj, Marko Bajec

Publication date 20 September 2018

Published in Physica A (Search for Journal in Brave)

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

zbMATH Keywords

clusteringcomplex networksgroup detectionhierarchy discoverylabel propagation

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Complex real-world networks commonly reveal characteristic groups of nodes like communities and modules. These are of value in various applications, especially in the case of large social and information networks. However, while numerous community detection techniques have been presented in the literature, approaches for other groups of nodes are relatively rare and often limited in some way. We present a simple propagation-based algorithm for general group detection that requires no a priori knowledge and has near ideal complexity. The main novelty here is that different types of groups are revealed through an adequate hierarchical group refinement procedure. The proposed algorithm is validated on various synthetic and real-world networks, and rigorously compared against twelve other state-of-the-art approaches on group detection, hierarchy discovery and link prediction tasks. The algorithm is comparable to the state of the art in community detection, while superior in general group detection and link prediction. Based on the comparison, we also dis- cuss some prominent directions for future work on group detection in complex networks.

Recommendations

• Community discovery algorithms: an overview
• Detecting network communities: a new systematic and efficient algorithm
• scientific article; zbMATH DE number 7234180
• Community detection in networks using new update rules for label propagation
• Finding community structure in networks using a shortest-path-based k-means algorithm

Cites work

• Collective dynamics of `small-world' networks
• Community structure in social and biological networks
• Emergence of Scaling in Random Networks
• Fast unfolding of communities in large networks
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 46578 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• Mixing patterns and community structure in networks
• Mixture models and exploratory analysis in networks
• Regular equivalence: General theory
• Role models for complex networks

Cited in

(8)

• Label propagation algorithm for community detection based on node importance and label influence
• Visualizing network communities with a semi-definite programming method
• Robustness and percolation of holes in complex networks
• Clustering method based on the elastic energy functional of directed signed weighted graphs
• Community detection with the label propagation algorithm: a survey
• Weighting dissimilarities to detect communities in networks
• scientific article; zbMATH DE number 5663542 (Why is no real title available?)
• Formal entity graphs as complex networks: assessing centrality metrics of the archive of formal proofs

This page was built for publication: Group detection in complex networks: an algorithm and comparison of the state of the art

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