Community Detection in Social Networks
Community structure is one of the essential properties of social networks. That is, the users can be divided into groups within which the communications are dense while between which the communications are sparse. This modular structure can disclose important cues, especially in online social networks, metabolic interaction networks, WWW, wireless sensor network and viral marketing, and facilitate creation, representation and transfer of knowledge and influence. For lack of standard and exact definition of community structure of social networks, we take the factors of time complexity and effectiveness into account and design community detection algorithms adjusted to various application situations. In this dissertation, based on exiting popular community detection methods, several innovative methods and ideas were proposed, including Global Influence-based Maximum K-Community Partition (GI-MKCP), Degree-based Terminal-Set-Enhanced Community Detection (TSECD-D), Influence-based Modularity Maximization and Competitive Influence Maximization Game-based community detection. Due to the NP-hardness of general community detection problems, our proposed algorithms can be executed in polynomial time and approximate the optimal solution. More importantly, validated and demonstrated by the experiments performed on benchmark networks, the proposed algorithms are able to generate high-quality community structures and outperform existing algorithms.