Research And Application Of The Generalized Framework For Community Detection

Revealing the latent community structure is a particularly challenging problem in complex network analysis and graph data mining. Since the increasing popularity of social networks, detecting communities in social networks can help us understanding the features of user behaviours and further analyzing the characteristics of group members.Since the community itself has no quantitative definition, a large number of methods have been proposed by di?erent researchers to solve this problem in diverse ways, i.e. di?erent data structures or di?erent problem-solving perspectives. Unfortunately, considering the adaptabilities to datasets or the characteristics of produced communities, the excessive existing approaches make it a puzzle to choose the best approach in a specific application.Therefore, in this thesis, based on the generalized framework for community detection,we study the evaluations, improvements as well as recommendations of various kinds of community detection algorithms. The primary contributions are summarized as follows:1. We propose a universal procedure-oriented framework for community detection(CoDFM), which is beneficial in understanding, analyzing and comparing the existing approaches. Firstly, by diving deeply into the formation of communities, we abstract the fundamental concepts in this problem, i.e. the propinquity measure and the revelatory structure. In addition, we formulate and propose a generalized community detection procedure via the modularized phases and steps in this procedure. Besides, we map and re-implement 10 state-of-the-art community detection algorithms in this framework to validate the rationality and validity of the framework.2. Based on CoDFM, we conduct in-depth evaluations and analyses of the various approaches systematically and thoroughly from multiple aspects, including the e?ciency of algorithms, quality, sensitivity, coverage ratio, and distribution of communities. Upon that we draw a set of interesting take-away conclusions about the characteristics and adaptabilities on the concerned algorithms, which help us to choose the most appropriate one according to di?erent datasets and scenarios to get the optimal community structures.3. Upon the universal framework, we analyze and diagnose the inherent defect of the existing approaches deeply, and further make e?ective improvements correspondingly. Based on diagnosing on key factors and steps, we propose the improved matrix blocking dense subgraph extract algorithm MB-DSGE* and the improved label propagation algorithm LPA*. Su?cient experimental results show that these algorithms can result in significant improvements.4. As the extension and visualization of the above work, we build the CoDAR system, which reveals the generalized procedure of community detection and monitors the real-time structural changes of network during the detection process. Moreover, it adopts a multi-dimensional rating model for quality evaluation of communities to recommend the best-performing algorithm to users. The system is quite useful for research and product development.