Wednesday, August 31, 2016

"Null Models for Community Detection in Spatially Embedded, Temporal Networks"

Another one of my papers finally got its volume, issue, and page numbers last week. (It came out in advanced access in November 2015.) I finally got my own copy of the document today, so here are some details.

Title: Null Models for Community Detection in Spatially Embedded, Temporal Networks

Authors: Marta Sarzynska, Elizabeth A. Leicht, Gerardo Chowell, and Mason A. Porter

Abstract: In the study of networks, it is often insightful to use algorithms to determine mesoscale features such as 'community structure', in which densely connected sets of nodes constitute 'communities' that have sparse connections to other communities. The most popular way of detecting communities algorithmically is to maximize the quality function known as modularity. When maximizing modularity, one compares the actual connections in a (static or time-dependent) network to the connections obtained from a random-graph ensemble that acts as a null model. The communities are then the sets of nodes that are connected to each other densely relative to what is expected from the null model. Clearly, the process of community detection depends fundamentally on the choice of the null model, so it is important to develop and analyse novel null models that take into account appropriate features of the system under study. In this paper, we investigate the effects of using null models that incorporate spatial information, and we propose a novel null model based on the radiation model of population spread. We also develop novel synthetic spatial benchmark networks in which the connections between entities are based on the distance or flux between nodes, and we compare the performance of static and time-dependent versions of the radiation null model to the standard ('Newman–Girvan') null model for modularity optimization and to a recently proposed gravity null model. In our comparisons, we use both the above synthetic benchmarks and time-dependent correlation networks that we construct using countrywide dengue fever incidence data for Peru. Our findings illustrate the need to use appropriate generative models for the development of spatial null models for community detection.

No comments: