Uncovering space-independent communities in spatial networks

By Paul Expert, Tim S. Evans, Vincent D. Blondel, Renaud Lambiotte. Proceedings of the National Academy of Sciences of the United States of America, 2010

346 citations recorded by the source corpus.

Many complex systems are organized in the form of a network embedded in space. Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks, and social networks. The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geolocalization, which constantly fill databases with people’s movements and thus reveal their trajectories and spatial behavior. Extracting patterns and regularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially embedded networks. In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology. In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks. We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes. Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics, Transportation

View Paper: https://www.semanticscholar.org/paper/31f97605dcb8874f539514762637fe3aecf1dc2f

How researchers see this paper

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

In Computer Networks and Communications

In Statistical and Nonlinear Physics

In Transportation

Citations in the corpus

Human mobility: Models and applications (2017, background): “applications in estimating other spatial flows, including cargo shipping volume [153] and social interactions from inter-city phone calls [124,154].”
Modular Brain Networks (2015, methodology): “If one is using modularity maximization for community detection, this issue can in part be addressed by modifying the connectivity null mode, p ij , so that the expected density of connections depends on distance (Expert et al. 2011).”
Geo-located Twitter as proxy for global mobility patterns (2013, background): “2009; Jung, Wang, and Stanley 2008; Zipf 1946) but also human interaction networks (Expert et al. 2011; Krings et al. 2009).”
Small-World Brain Networks Revisited (2016, methodology): “Third, the metric is informed by spatially-constrained null models [92–94] in which nodes have physical locations and the edges that correspond to the smallest Euclidean distance between nodes are assigned the highest weights [95] (Fig 5).”
Smart cities of the future (2012, neutral): “Generally, social structures of communities detected from phone data analysis show strong spatial regularity in regional [20] and city scale levels [45], revealing finer patterns concerned with cultural and socio-economic heterogeneity of cities.”
Nine quick tips for analyzing network data (2019, neutral): “, spatial [10] or phylogenetic effect [11]).”
Community detection in networks: A user guide (2016, background): “Other choices of the null model term allow us to incorporate specific features of network structure, like bipartiteness [147], correlations [148], signed edges [149], space embeddedness [150], etc.”
Uncovering Patterns of Inter-Urban Trip and Spatial Interaction from Social Media Check-In Data (2013, methodology): “sconnected (i.e. with enclaves). Community detection methods are therefore extended to take into account specific spatial characteristics, such as adjacency constraint (Guo 2009) and distance effect (Expert et al. 2011), for supporting regionalization. However, there is some research directly uses c”
Spatial Science and Network Science: Review and Outcomes of a Complex Relationship (2014, background): “Expert et al. (2011) adapted a modularity function – modularity being a measure of clustering quality – to spatial networks in order to better understand the influence of the spatial factor on network structure, with an application to Belgian mobile phone communication flows between individuals.”