Community Detection And Structural Analysis In Complex Networks Based On Graph Theory

Network science is one of the most powerful tools for studying the relationship among the things of real world systems. Modeling complex systems as complex networks, the things among complex systems as vertices, while their relationships among those things as edges are the premise to make further analysis of the things of real world systems. Exploring the hidden knowledge is the urgent task in the modeled complex networks and specifically exploring the related components and their physical significance. And in other words, the task is how to detect metadata groups in complex networks and a metadata group is the vertex set that having same or similar functions or roles in complex networks. We can get metadata groups by the way of experimental verification, while this enumerating verification is always infeasible facing to current vast amount of data. Thus researchers turn to computational methods and general steps are to model the complex system as complex networks, define metadata groups as corresponding communities or modules and then develop algorithms to detect the so called communities or modules in the modeled complex networks. It is easy to get metadata groups in complex networks based on computational methods. And in essence, there are two core tasks within computational methods. One is that how to define communities, in other words, what can the metadata groups of networks be described? And the other is that how to detect the defined communities effectively.The related researches in this dissertation are mainly arround the two core tasks about community detection. Edge anti-triangle centrality and the corresponding algorithm EACH, Cograph community and the corresponding algorithm EPCA,2-club community, the algorithm DIVANC and analysis of the functional modules in PPI networks based on 2-club community are proposed from the viewpoint of graph theory. The main contributions are described as follows:1. The current research about community detection algorithms is maninly developed based on dense subgraphs. Paying more attention to designing related indices for measuring embeddness of communities while little attention to the sparsity outside communities. This dissertation gives edge anti-triangle centrality from the viewpoints of tangent paths and further propose the corresponding communtiy detection algorithm EACH. Edge anti-triangle centrality is defined as the ratio of the number of P4 to which a given edge belongs divided by the number of potential P4 that might include it. EACH iteratively remove the edges with highest anti-triangle centrality until the anti-triangle centralities of all the current edges turn into zero, then output the current connected components with isolated vertex handing strategy. By comparison with other competitive algorithm, EACH is simle, effient, and the detected communities are compact with significant physical functions.2. We may ignore their inner topological structures if we mainly describe metadata groups as dense subgraph. The inner topological structures of metadata groups are very important to understand their function formation mechanisms and operation patterns. In order to explore the topological relationships among those vertices of metadata groups, we describe metadata groups as the defined Cograph community which is a connected subgraph without containing induced subgraph P4 in this dissertation. A Cograph community structure uniquely correspond its Cotree and based on Cotree, we can demonstrate the structural equivalent subgroups within Cograph community. We also develop the algorithm EPCA to detect Cograph communities based on the proposed edge P4 centrality. Edge P4 centrality is defined as the number of P4S to which that given edge belongs and a P4 is an induced graph on 4 ordered vertices which are connected as a simple path. According to the meaning of P4 centrality, if its P4 centrality is large, it is more likely to be an inter-link, while if its P4 centrality is smaller it is more probably an intra-link. EPCA iteratively removes the edge with highest edge P4 centrality score, until the scores of the remaining edges are all zero and outputs the current connected components as Cograph communities. EPCA has low computational cost, is free of parameters and does not need any additional measures are mainly due to the proposed local edge P4 centrality.3. The main challenge lies in the fact that traditional structural communities do not always capture the intrinsic features of metadata groups. Motivated by the observation that metadata groups in PPI networks tend to consist of an abundance of interacting triad motifs, we define a 2-club community with diameter 2 which possessing triad-rich property to describe a metadata group. We also design a division algorithm DIVANC using the proposed edge niche centrality to detect metadata groups effectively in complex networks. DIVANC is also extended to detect overlapping metadata groups by proposing a simple 2-hop overlapping strategy. Niche centrality is used to distinguish the inter-links from intra-links which is proposed based on two basic topological components:circles and paths. According to the meaning of niche centrality, if its niche centrality is large, it is more likely to be an inter-link, while if its niche centrality is smaller it is more probably an intra-link. DIVANC iteratively removes the edge with highest edge niche centrality score, until the scores of the remaining edges are all zero and outputs the current connected components as non-overlapping 2-club communities, while if continue implementing 2-hop overlapping strategy, it can output overlapping 2-club communities.4. Thoroughly understanding functional modules in PPI networks is still one of the foremost challenges in the research of system biology. Currently many analyses of functional modules in PPI networks mainly focus on the approaches of how to detect them, but pay little attention to their inner topological structures and correlating them with their roles in entire PPI networks. In this dissertation we analyze the inner topological structures of functional modules based on graph theory. And we further show their related properties distribution and try to infer their roles for the detected modules in PPI networks. The method based on graph theory provides a novel way of understanding the organizations and property distributions of modules in PPI networks.