Community Detection using a Measure of Global Influence
arXiv:0805.4606
Abstract
The growing popularity of online social networks has provided researchers with access to large amount of social network data. This, coupled with the ever increasing computation speed, storage capacity and data mining capabilities, led to the renewal of interest in automatic community detection methods. Surprisingly, there is no universally accepted definition of the community. One frequently used definition states that ``communities, that have more and/or better-connected `internal edges' connecting members of the set than `cut edges' connecting the set to the rest of the world''[Leskovec et al. 20008]. This definition inspired the modularity-maximization class of community detection algorithms, which look for regions of the network that have higher than expected density of edges within them. We introduce an alternative definition which states that a community is composed of individuals who have more influence on others within the community than on those outside of it. We present a mathematical formulation of influence, define an influence-based modularity metric, and show how to use it to partition the network into communities. We evaluated our approach on the standard data sets used in literature, and found that it often outperforms the edge-based modularity algorithm.
10 pages, submitted to 2008 KDD workshop on Social Network Analysis
References in corpus (7)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Community structure in directed networks
- Finding local community structure in networks