Ordered community structure in networks

Abstract

Community structure in networks is often a consequence of homophily, or assortative mixing, based on some attribute of the vertices. For example, researchers may be grouped into communities corresponding to their research topic. This is possible if vertex attributes have discrete values, but many networks exhibit assortative mixing by some continuous-valued attribute, such as age or geographical location. In such cases, no discrete communities can be identified. We consider how the notion of community structure can be generalized to networks that are based on continuous-valued attributes: in general, a network may contain discrete communities which are ordered according to their attribute values. We propose a method of generating synthetic ordered networks and investigate the effect of ordered community structure on the spread of infectious diseases. We also show that community detection algorithms fail to recover community structure in ordered networks, and evaluate an alternative method using a layout algorithm to recover the ordering.

This is an extended preprint version that includes an extra example: the college football network as an ordered (spatial) network. Further improvements, not included here, appear in the journal version. Original title changed (from "Ordered and continuous community structure in networks") to match journal version

References in corpus (9)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Dynamics of person-to-person interactions from distributed RFID sensor networks
• Uncovering space-independent communities in spatial networks
• Modularity clustering is force-directed layout
• Who is the best player ever? A complex network analysis of the history of professional tennis

Cited by in corpus (2)

• Exponential random graph models for networks with community structure
• Spatial correlations in attribute communities