Community Detection in Networks with Node Attributes

By Jaewon Yang, Julian McAuley, Jure Leskovec. 2013

898 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Debiasing Community Detection: The Importance of Lowly Connected Nodes (2019, methodology): “We use two state-of-the-art approaches, CESNA [21], and the Louvain method [3].”
Community detection in Attributed Network (2018, background): “However, considering both node attributes and network topology for community detection is also challenging, as the approach have to combine two types of information [33].”
Attributed Graph Clustering via Adaptive Graph Convolution (2019, methodology): “Some methods model the interaction between graph connectivity and node features with generative models [ Chang and Blei, 2009; Yang et al. , 2013; He et al. , 2017; Bojchevski and G ¨ unnemann, 2018 ] .”
Spanning Tree Based Community Detection Using Min-Max Modularity (2016, neutral): “w(u, v) = Cneigh(u, v) +Cedges(u, v) Tneigh(u, v) +Cneigh(Cneigh − 1)/2 (11)”
Structure and inference in annotated networks (2015, methodology): “Perhaps closest to our approach are the semi-supervised learning methods [13–15], which treat the case where we are given the exact community assignments of some fraction of the nodes and the goal is to deduce the reminder.”
Community detection in networks: A user guide (2016, neutral): “19 et al., 2015; Leng et al., 2013; Moore et al., 2011; Peel, 2015; Yang et al., 2013).”
Tracing Fake-News Footprints: Characterizing Social Media Messages by How They Propagate (2018, methodology): “The second term aims to achieve the intra-group coherence by predicting the community assignment by group the embedding vectors of users and communities [44].”
A survey of community search over big graphs (2019, background): “el. In [193], the attributed graph is clustered based on probabilistic inference. In [166], the topics, interaction types, and the social connections are considered for discovering communities. CESNA [199] detects overlapping communities by assuming communities \generate" both the link and cont”
Clustering attributed graphs: Models, measures and methods (2015, background): “Recently, Yang et al. (2013) have used node attributed graphs for detecting overlapping communities, stating that the resulting communities can be interpreted more easily by analyzing the attributes of the nodes belonging to each community.”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “1), platform sponsors promote products to targeted users in detected communities [23], [24].”
Bayesian Robust Attributed Graph Clustering: Joint Learning of Partial Anomalies and Group Structure (2018, methodology): “Among the non-robust methods, PICS (Akoglu et al. 2012), CESNA (Yang, McAuley, and Leskovec 2013) and SIAN (Newman and Clauset 2016) only derive point-estimates of the learned parameters.”
Scalable and Interpretable Product Recommendations via Overlapping Co-Clustering (2016, methodology): “ing a model that generates both node attributes and edges in the corresponding graph with communities by regarding the community afﬁliation vectors as the inputs features to a (binary) logistic model [46]. In the same way, we assume that the A i are generated by the co-clusters by regarding the co-c”
Network Representation Learning: A Survey (2017, background): “However, network representation learning tailored to many other important network analysis tasks like link prediction [12], community detection [78], and anomaly detection [79], has not been extensively investigated.”