Detecting overlapping communities from micro blog network by additive spectral decomposition

Abstract

Detecting community structure is critical in analysing social networks which are flourishing and influencing every aspect of people’s social life. Most social network systems are composed with complicated entity relations such and social interests, user relationships and their interactions. To understand how users interact with each other under the community level, its not enough to consider one kind of these relations while ignore the other. An united network model that can comprehensively integrate these relations is essential for community detection. Focusing on such kind of problem when dealing with social network with multiple relations, this paper proposes a heterogeneous network model which characterizes and constructs user similarity relations by combining both of users’ interests and their interactions attributes. Based on the heterogeneous similarity model, an additive spectral decomposition algorithm is applied to detect overlapped communities from the network. The remarkable effect of our heterogeneous model is the ability to reveal most important attributes of the blog network. And, comparing to crisp clustering method, the additive spectral decomposition algorithm proposed is effective for finding overlapped user groups which is more reasonable among social networks where users tend to join multiple social groups. Results of experimental studies on real-world and synthetic datasets demonstrate the effectiveness of the algorithm with respect to the size, the distributive structure and the high dimensionality of the datasets.