Structural Pattern Mining And Diffusion Dynamical Model In Complex Network

With the widely applied of complex network in many different fields, such as computer science, sociology, physics, bioinformatics, genetic engineering, the quantity of applications and generated data based on complex networks has been increased rapidly. Due to some features in complex network data, like complexity, irregularity, and high capacity, traditional data mining methods are no longer suitable for analyzing complex networks. Therefore, some data mining techniques fit for complex networks are required.At present, the research of data mining technologies for complex networks is still in its infancy. Part of research achievements have been made in structural pattern mining and diffusion dynamics in complex networks. However, most of these studies are relative independent, decentralized, high repeatability, and insufficient nonobjectivity, have not formed a unitary system. In this paper, the theories and methods of data mining in complex networks are studied and summarized, processes are analyzed, and fundamental mining procedures and framework are established for complex network data. On this basis, some technologies for complex networks, such as summarizing, subgraph matching, and diffusion dynamical model, are studied and discussed in-depth, respectively.(1) Research on fundamental data mining framework for complex networksBased on the characteristics of information in complex networks, combined with traditional data mining procedures, a nonobjective and unified data mining procedure and framework are proposed for complex networks. Furthermore, basic concepts and definitions of complex networks are proposed and analyzed, and classic topological structures and features of complex networks are presented. From the perspective of macro and micro behavior, information diffusion in complex networks is introduced.(2) Research on summarizing complex networks based on virtual and real linksBased on the analysis of multi-valued attributes and topological structure in complex networks, a unified framework based on the concept of virtual graph is proposed by integrating attributes and structural similarities in this paper. We propose the SGVR approach (Summarizing Graph based on Virtual and Real Links) for summarizing complex networks, to aggregate similar nodes into k non-overlapping groups considering both virtual links (attributes) and real links (graph structures). During implementation, a data structure HB-Graph as well as an effective adjusting subgroup method is adopted, to optimize grouping results. In addition, we achieve multi-resolution of summaries using user-selected attributes and stack-based recording technique. The experimental results show that our proposed method is both effective and efficient than other state-of-the-art algorithms.(3) Research on subgraph matching based on neighborhood trees for complex networksFor graph matching problem in complex networks, graph matching framework based on structural pattern is proposed. A new graph indexing mechanism known as Neighborhood Trees (NTree) are introduced, which records the neighborhood relationships of each vertex in large graphs to prune query results and filter negative vertices. In addition, canonical unordered trees are leveraged, and the string comparison technique is used to accelerate the subtree containment process. Moreoever, a graph query cost model is designed on the problem of neighborhood tree selection to optimize the search order. The experiments are evaluated under different structural patterns, the results show that our indexing method, NTree, has more powerful pruning and reconstructing capacity. Experiments on both real and synthetic databases demonstrate that our proposed approach is more efficient than other latest indexing methods in graph matching.(4) Research on diffusion dynamical model based on sentiment analysis in complex networksFor information diffusion prediction problem in complex networks, an emotion-based spreader-ignorant-stifler (ESIS) model is proposed. Sentiment analysis method is adopted to classify information cascades into fine-grained classes. Each emotion is assigned with corresponding retweeting strengths by calculating edge weights in complex networks. Furthermore, mean-field equations are adopted to calculate threshold of information diffusion for each emotion, and also final size of stiflers. We verify the proposed model and predict spreading results, and the experiement results indicate that happiness spreads most widely, while anger has the lowest proportion in information diffusion.