Detecting cohesive and 2-mode communities indirected and undirected networks

By Jaewon Yang, Julian McAuley, Jure Leskovec. 2014

83 citations recorded by the source corpus.

Networks are a general language for representing relational information among objects. An effective way to model, reason about, and summarize networks, is to discover sets of nodes with common connectivity patterns. Such sets are commonly referred to as network communities. Research on network community detection has predominantly focused on identifying communities of densely connected nodes in undirected networks. In this paper we develop a novel overlapping community detection method that scales to networks of millions of nodes and edges and advances research along two dimensions: the connectivity structure of communities, and the use of edge directedness for community detection. First, we extend traditional definitions of network communities by building on the observation that nodes can be densely interlinked in two different ways: In cohesive communities nodes link to each other, while in 2-mode communities nodes link in a bipartite fashion, where links predominate between the two partitions rather than inside them. Our method successfully detects both 2-mode as well as cohesive communities, that may also overlap or be hierarchically nested. Second, while most existing community detection methods treat directed edges as though they were undirected, our method accounts for edge directions and is able to identify novel and meaningful community structures in both directed and undirected networks, using data from social, biological, and ecological domains.

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

Dropout Training of Matrix Factorization and Autoencoder for Link Prediction in Sparse Graphs (2015, background): “non-cohesive distinction of graph structure has previously been investigated in [29, 9].”
SNAP: A General Purpose Network Analysis and Graph Mining Library (2016, methodology): “This method has been extended in several directions to cover networks with millions of nodes and edges [Yang and Leskovec 2013], networks with node attributes [Yang et al. 2013], and 2-mode communities [Yang et al. 2014].”