On Inconsistencies in Quantifying Strength of Community Structures

Chong, W.H.

    Complex network analysis involves the study of the properties of various real world networks. In this broad field, research on community structures forms an important sub area. The strength of community structure is typically quantified by the modularity measure. The measure is based on summing the differences in actual and expected fraction of edges per community (across all communities in the network), whereby the latter is computed based on randomizing the edges subjected to certain constrains. In this paper, we investigate the differences between two commonly used definitions of modularity and highlight one of them as inadequate for quantifying the strength of community structures. We first show this by mathematical proving. We then investigate the empirical differences by developing and testing two variants of a community detection algorithm whereby the variants differ based on their modularity definitions. We observe varying differences in detection accuracy when applying the variants on artificially generated networks. For networks with strong community structures, we show that sensible results are still obtainable with the inadequate measure, which explains why this issue did not come to light previously
Cite as: Chong, W.H. (2008). On Inconsistencies in Quantifying Strength of Community Structures. In Proc. Seventh Australasian Data Mining Conference (AusDM 2008), Glenelg, South Australia. CRPIT, 87. Roddick, J. F., Li, J., Christen, P. and Kennedy, P. J., Eds. ACS. 21-26.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS