Research On Large-Scale Complex Network Visualization Based On Community Detection

Recent years, academic research on complex network has been a veryhot topic. Its rapid development has further our understanding of realcomplex network systems. In a complex network, communities are groupsof nodes that are densely connected inside while sparsely connected to theoutside. The study of such communities is crucial in exploring the structureof a network. So far, visualization tools designed for complex networkanalysis are very common, with each targeting at different research tasks.But only a few of them could visualize the hierarchical and overlappingcommunity structure, which is essential for further exploration of thenetwork structure and dynamics.To study the community structures of complex networks, this thesisconducted researches on the hierarchical and overlapping communitystructure detection, with emphasis on visualization methods used forlarge-scale complex network based on community detection. To do ourresearch, firstly, we conducted a comparative analysis on some popularcomplex network visualization tools at home and abroad. Secondly, wediscussed the hierarchical and overlapping community structures.Considering the facts that community structures of many real networks arecommonly hierarchical and overlapping, thus this thesis conductedresearches on the hierarchical and overlapping community structuredetection at the same time. Accordingly, we proposed an algorithm touncover the hierarchical and overlapping community structures based ongreedy strategies. Thirdly, based on our understanding of existing complexnetwork visualization technologies, this thesis proposed a visualization method for hierarchical community partition and fence-sitting nodesdetection based on community detection algorithms. Besides, we used Javaand successfully developed a platform for large-scale complex networkvisualization, named as Visualization based on Community Detection(VCD).Contributions that this thesis made include:1. We conducted a comparative analysis on some representative complexnetwork visualization tools. Based on the fact that a universal standardfor complex network visualization is not yet established, we introducedthe CIShell framework and summarized the use and development ofsuch tools;2. We proposed an algorithm to uncover the hierarchical and overlappingcommunity structures of sparse networks. This algorithm is a greedyagglomerative clustering algorithm that aggregates nodes with intenseconnection step by step until reaching the optimal modularity, resultingin a hierarchical community structure. But different from otherhierarchical community detection algorithms, our algorithm enablesnodes to belong to single or multiple communities at the same time;3. We proposed a visualization method for hierarchical communitypartition and fence-sitting nodes detection, which is based on themodularity optimization oriented community detection algorithm. Thismethod could not only unveil the topological structure of the targetnetwork but also display network community structure and fence-sittingnodes by abstraction, which successfully avoids the commonoverlapping problems in the research of large-scale networkvisualization;4. The proposed VCD platform integrates both the circular and clusteringlayouts. It could not only simulate the evolution of a network’shierarchical community structure but also integrate Cover Flowtechnology that is widely used in mobile platform into the visualizationof network community structure. VCD provides users with several kinds of visualization: visualization for community structure andvisualization for overlapping nodes. The former visualization couldvisualize the relationship of the communities detected, while the lattervisualization could visualize overlapping nodes. Besides, this platformis highly interactive, enabling users to view the target network indifferent ways.