Is Modularity the Answer to Evaluating Community Structure in Networks?

Karsten Steinhaeuser, Nitesh V. Chawla
Steinhaeuser, Karsten, and Nitesh V. Chawla. "Is Modularity the Answer to Evaluating Community Structure in Networks?." International workshop and conference on network science (NetSci’08), Norwich Research Park, UK. 2008.
Publication Date: 
June, 2008

One important task in network analysis is that of community detection, or partitioning of a network into groups of nodes that belong together. The problem is relevant to a variety of application areas, but social networks in particular have been the subject of research at the intersection of physics, computer science, and the social sciences. In this context the notion of community is intuitive to grasp, but there is no consensus on a formal definition of the concept. Our work addresses this issue in two primary ways:

(i) We examine modularity (Newman, 2004) as both an evaluation measure of community structure as well as an optimization criterion used by some algorithms to identify communities in networks (Clauset, 2004; Duch, 2005). Specifically, we assess the pros and cons of modularity, and identify its shortcomings via comparison to alternate evaluation metrics on networks for which the true communities are known.

(ii) We develop a simple method for community detection using random walks (Figure 1) and show that it can identify the actual communities at least as well as more complex algorithms (Table 1).

We further expand upon the idea of community detection with random walks by extending the method to weighted networks and explain how to incorporate node attributes – information that is frequently available but usually ignored by other algorithms – to compute edge weights that can aid in detecting more meaningful communities. To demonstrate the scalability of the random walk approach and examine the effect of using node attributes for edge weighting, we apply the method to a real-world social network constructed from cell phone records consisting of 1.3 million customers.