Research On Key Technologies Of Large-scale Network Visualization

In recent years,the complex network analysis studies have shown that a large number of real networks such as social network,transport network,citation network,protein networks etc.are associated with nontrivial topological characteristics.The main goal of complex network analysis is to detect and find these structures to help people understand the laws.Network visualization is an important support technology to realize the above goals and also a branch research field of information visualization.Quickly and efficiently,multi-scale visualization of the network topology,lower complexity,for network analysts go through efficient and intuitive found in implicit rule or trend,has become the important research subject.With the rapid expansion of network scale,the network structure is complex and diverse,and traditional network visualization methods,including network community detection,network compression,network layout and others,are difficult to meet the actual demand.Therefore,this dissertation is committed to large-scale network visualization technology research,decomposed into "network structure feature detection-network structure layout”,to solve the following four aspects of specific issues:(1)rapid detection of overlapping community structure in large scale network structure;(2)network topology detection and characterization of higher-order dependencies;(3)efficient visualization of large scale network global structure with multiple hierarchical compression structures;(4)fast,lossless visualization of local high density network.Specific research work is as follows:Current existing overlapping community detection algorithms may falsely identify overlaps as communities because the overlap area is denser than others,and those algorithms are computationally demanding and cannot scale well with the size of networks.In this paper,we propose a fast overlapping community discovery algorithm based on some locally computed information—Local information based Fast Overlapping Communities Detection(Li-FOCD).Firstly,we introduce two local information metrics for each network node—community connectivity score and neighborhood connectivity score,to measure the relationship between nodes and communities;secondly,based on local metrics,we can concurrently execute the iterations of reduction,expansion,and duplication removal to find the approximately optimal communities instead of the optimal communities,and achieve a low complexity O(7)m(10)n(8).Experimental analysis based on real large-scale social network datasets shows that our algorithm outperforms some popular overlaping community detection algorithms in terms of computational time while not compromising with quality.Clustering is one of important approaches to structure the relationship in large-scale network.However,high-order(rather than pairwise)similarities and the number of clusters in the real network are the key problems.Thus we propose a novel clustering approach based on the evolutionary game theory.First,hypergraph is introduced to unearth the high-order similarities among network elements;then,we use evolutionary game theory to model the hypergraph clustering process,and theoretically prove that the equilibrium point is equivalent to the solution of the optimization problem,and deduce the dynamical equation to recursively caculate the clusters.Our algorithm does not need to set the number of clusters.The experiments on the synthesized datasets and real datasets show that the proposed algorithm can automatically detemine the number of clusters,and provides good clustering quality and strong robustness.As an important network visualization technical,network compression can show multiple global network structure of large scale networks.To show the hierarchical structures quickly with different scales,this paper proposed a hierarchical network compression algorithm based on splitting and merging unimportant nodes.The algorithm firstly proposed a method to measure the importance of different node blocks based on the definition of node blocks and connections between them.Then,motivated by the process of resource allocation,it proposed a hierarchical aggregation mechanism based on node splitting.Finally,it can quickly compress the network by splitting and merging unimportant nodes in each hierarchical structures compression.Experiments on real networks have shown that the algorithm proposed can achieve a good performance on visualization with multiple hierarchical compression structures,compared with other methods.Recent studies have shown that lossless compression of this high-density network graph makes network routing and link prediction easy.However,it is difficult to calculate the optimal power graph.To solve this problem,firstly,we prove that the optimal power graph problem with single module is a NP-hard,and then extend this conclusion to the generally optimal power graph decomposition;secondly,upon analyzing the existing approaches such as integer linear programming model and constraint programming model,this paper presents a customized search method---the beam search algorithm.By further introducing the backtracking strategy,the algorithm provides a limited heuristic backtracking strategy,and gets better results much faster than well-known heuristic methods;finally,by generating a random scale-free graph,we verify our proposed algorithm.