ComputingBioinformaticsCommunity AssessmentGraph VisualizationNetwork BiologyCommunity DetectionCommunity StructureGraph MiningNetwork AnalysisNetwork StructureSocial Network AnalysisNetwork Community DetectionOverlapping Community DetectionRobust Community DetectionRuntime OptimizationScalable Community Detection
Community detection algorithms uncover organizational principles in networks and can use either network structure or node attributes, yet most methods focus on only one modality. This paper introduces CESNA, an accurate and scalable algorithm for detecting overlapping communities in networks with node attributes. CESNA statistically models the interaction between network structure and node attributes, yielding more accurate community detection, robustness to structural noise, and interpretable attribute associations for each community. CESNA achieves linear runtime, scales to networks an order of magnitude larger than comparable approaches, and improves robustness to noise while providing attribute‑based community interpretation.
Community detection algorithms are fundamental tools that allow us to uncover organizational principles in networks. When detecting communities, there are two possible sources of information one can use: the network structure, and the features and attributes of nodes. Even though communities form around nodes that have common edges and common attributes, typically, algorithms have only focused on one of these two data modalities: community detection algorithms traditionally focus only on the network structure, while clustering algorithms mostly consider only node attributes. In this paper, we develop Communities from Edge Structure and Node Attributes (CESNA), an accurate and scalable algorithm for detecting overlapping communities in networks with node attributes. CESNA statistically models the interaction between the network structure and the node attributes, which leads to more accurate community detection as well as improved robustness in the presence of noise in the network structure. CESNA has a linear runtime in the network size and is able to process networks an order of magnitude larger than comparable approaches. Last, CESNA also helps with the interpretation of detected communities by finding relevant node attributes for each community.
17
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
Hierarchical Clustering Schemes
S. C. Johnson · Psychometrika · 1967 · 4.9K citations
Applied Physics Letters · 2000 · 3K citations · Full text
Humanities, Biomedical Informatics, Language Documentation +7
Link communities reveal multiscale complexity in networks
Yong‐Yeol Ahn, James P. Bagrow, Sune Lehmann · Nature · 2010 · 2K citations · Full text
The Focused Organization of Social Ties
Scott L. Feld · American Journal of Sociology · 1981 · 1.9K citations