Research On Algorithms For Mining Cograph Communities And 2-club Communities

The current development of science and technology in various fields has produced massive amounts of actual field data.The analysis and interpretation of these data faces the fundamental problem of how to characterize the relational data.In scientific practice,people gradually use complex network to represent various relational data,such as biological networks in biological problems,social networks and traffic networks.Exploring these complex networks and finding meso-scale structures of practical significance from these networks is one of the key issues in the research of network science.The detected meso-scale structures can clearly show the local structural characteristics of the networks,which in turn enables people to understand the various complex relationships.Therefore,it is important to study how to mine the meso-scale community structures within large-scale complex networks.This thesis mainly focuses on the two core scientific contents of communitydetection,namely how to define a community and design the corresponding algorithms for community detection.The community structures defined from the perspective of density is widely used.The edge density within the community is high,while,the edge density between different communities are sparsely connected.In this thesis two new community structures:Cograph communities and 2-club communities are introduced,and three corresponding algorithms for community detection are designed.The main research contents are described as follows:(1)The structures of Cograph communities and their corresponding detection algorithms.The structure of Cograph community does not only have the traditional property of internal tightness and outside looseness,but also the characteristics that can be transformed into the corresponding Cotree.The structure of Cotree can demonstrate a clearer hierarchical relationship of the members within Cograph community.From the perspective of iterative edge deletion,this thesis proposes an algorithm for detecting Cograph communities called ECFo P,which iteratively deletes the edge with the lowest edge clustering coefficient(Edge Clustering Coefficient)until the obtained connected component no longer contains the P₄subgraph(Free of P₄),the connected components obtained are the Cograph communities.The experimental tests on social networks,human PPI networks and yeast PPI networks,are implemented with some of the current mainstream algorithms GN,CNM,MCL,INFOMAP,OSLOM and LOUVAIN.The experiments show that ECFo P can achieve competitive results on the PPI network,and the detected communities detected are Cograph communities with the fine structural characteristics.(2)The structure of 2-club communities and the corresponding algorithms for detecting them.The traditional community is defined on the basis of density,and does not have fine structural characteristics,so it cannot reveal the essential characteristics of the represented metadata groups.The 2-club community is proposed based on the characteristics of the rich interaction triples in the metadata group in the PPI networks.This thesis proposes two new algorithms for detecting 2-club communities:ECD2 and EPD2.ECD2,from the perspective of the edge clustering coefficient,iteratively deleting the edge with the largest edge clustering coefficient until the diameter of the connected branch is 2 hops,so that 2-club community is detected.EPD2,is proposed based on Edge P₄ centrality through iterative deleting the edges with the largest P₄ centrality,until the resulted connected components with the condition of diameter 2,and then 2-club community is detected.In this thesis the two algorithms are tested on social networks,the human and yeast PPI networks.The results show that the two algorithms do not only have competitive accuracy.