Community Structure in Time-Dependent, Multiscale, and Multiplex
  Networks

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

Network science is an interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. A prominent problem in network science is the algorithmic detection of tightly-connected groups of nodes known as communities. We developed a generalized framework of network quality functions that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices. This framework allows one to study community structure in a very general setting encompassing networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales.

Related collections

Most cited references 2

Record: found
Abstract: found
Article: found

Is Open Access

Community structure in social and biological networks

Michelle Girvan, M. Newman (2001)

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this paper, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well-known - a collaboration network and a food web - and find that it detects significant and informative community divisions in both cases.

0 comments Cited 1183 times – based on 0 reviews

Preprint

     Review now

Bookmark

Record: found
Abstract: found
Article: not found

Tracking evolving communities in large linked networks.

Brian Kulis, Bart Selman, Omar Khan … (2004)

We are interested in tracking changes in large-scale data by periodically creating an agglomerative clustering and examining the evolution of clusters (communities) over time. We examine a large real-world data set: the NEC CiteSeer database, a linked network of >250,000 papers. Tracking changes over time requires a clustering algorithm that produces clusters stable under small perturbations of the input data. However, small perturbations of the CiteSeer data lead to significant changes to most of the clusters. One reason for this is that the order in which papers within communities are combined is somewhat arbitrary. However, certain subsets of papers, called natural communities, correspond to real structure in the CiteSeer database and thus appear in any clustering. By identifying the subset of clusters that remain stable under multiple clustering runs, we get the set of natural communities that we can track over time. We demonstrate that such natural communities allow us to identify emerging communities and track temporal changes in the underlying structure of our network data.

0 comments Cited 47 times – based on 0 reviews      Review now

Bookmark

All references

Author and article information

Journal

Publication date Created: 09 November 2009

Publication date Updated: 2010-07-12

Article

DOI: 10.1126/science.1184819

ArXiV ID: 0911.1824

SO-VID: 69d37e6c-ba1f-4a98-9dc4-188cdc6d7b1a

License:

http://arxiv.org/licenses/nonexclusive-distrib/1.0/

History

Custom metadata

Journal reference Science vol.328, 876-878 (2010)

Comments 31 pages, 3 figures, 1 table. Includes main text and supporting material. This is the accepted version of the manuscript (the definitive version appeared in Science), with typographical corrections included here

Categories physics.data-an physics.soc-ph

Data availability: