Study On Structural Patterns Mining On Complex Networks

During the last decade. the development of digital technologies brings us powerful ability to compute and massive data to analyze, which are two factors encouraging researchers to explore the real-world systems more deeply. Complex networks, a recent general research paradigm which describes systems as a large number of interacting elements. provide the research community a new system-level perspective to real-world systems.Researcher community on complex networks, also called "new science of networks" believe that world is a combination of diverse systems, while these real-world complex systems in study consist of hundreds or thousands or more interacted units. Modeling the units as network nodes, and their interactions as edges, we can analyze the functions and properties of the studied systems by observing the produced networks.Researchers use statistical tools to study the topology of the real-world complex networks. They propose new measurements to depict the networks, build new models to fit the real-world data, and create new equations to simulate the dynamics on the networks. Researchers in the field of the complex networks had made a great development in the last decade.The origins of the complex networks study are graph theory and social network study, and the recent factors for development are real-world data and applications. Researchers struggle to mine detail information of the real-world networks. However, many traditional methods from the graph theory are not efficient on current large-scale datasets. To over the gap, research on network methodology is urgent.Along this direction, the contribution of this dissertation is analyzing network structural patterns from the data analysis perspective. Network structural patterns, say, community or hierarchy, root from node similarity, while statistical data analysis tools are sophisticated to extract the structural patterns in data distribution. In the text, we first project the studied network into a high dimensional measure space, converting the network analysis problems into data analysis ones, then use the signal process and pattern recognition tools to analyze the structure of the produced data distribution, and further infer network structural patterns from the structure of the data distribution. The experiments show7 that some network problems can be solved more conveniently.There are three main themes in this work. The first one is network topological patterns analysis. We project the studied network into a measure space, with similar nodes assigned to close positions in the measure space, and topological patterns of the original network emerge from the produced data point cloud. Follow this framework, we analyze the random, regular, small-world and scale-free networks,their distinctive characteristics are exhibited. We also use the real-world Internet autonomous systems networks as a case study. In the text, the proposed method also reproduces the hierarchy and jelly-like structure of the Internet. Based on the measurement of the produced data distribution, we study the network similarity. These experiments indicate that the present method is effective for network analysis.Second, the dissertation describes a novel method of community detecting on the complex networks. Community is one of the essential structures on real-world networks, associating with the functions and properties of the networks. Researchers have great interests in community detection. This work views communities as independent factors of the networks,and the proposed method identifies the communities from the clusters of the data points in the measure space. We apply the proposed community detecting method to two social networks, Zachary karate club network and Southern women network. From a new point of view, their communities are revealed effectively.Third, the dissertation presents network comparison based on the data analysis measurement. As structural regularities of the studied network are preserved in the properly produced data cloud, we extract representative distribution patterns from produced data clouds as network features. Based on these network features, we compare two kinds of real-world networks, and discuss their distinctive structural patterns. Similar networks cluster together. This proposed method can be a new approach to extract network features.These methods can be developed into a general framework. By importing sophisticated tools from the fields of signal process and pattern analysis into the network analysis field,the framework can provide more tools for network analysis,also more possibility to explore and explain network properties.