一种大规模双网络中k-连通Truss子图发现算法

Dual network is composed of physical and conceptual graphs with the same set of vertices while different sets of edges, which reflects different interactions between vertices. Cohesive subgraph discovery in dual network, aiming to find the subgraph connected in physical graph and cohesive in conceptual graph with a wide range of applications. e.g., co-author network analysis, community discovery and disease function cluster detection. Yet, existing models mainly have the following two limitations: (1) the cohesive subgraph discovery problem based on densest subgraph model is NP-hard in essence, which leads to low efficiency of accurate discovery algorithm; (2) although the k-core based model solves the efficiency problem, the cohesive subgraphs found are not really "cohesive". To overcome above limitations, in this paper, (1) the k-connected truss (k-CT) model is proposed, which is more cohesive and allows overlapping; (2) an efficient accurate sublinear algorithm is proposed to find all k-CTs; (3) the concept of maximum-connected truss (MCT) model is proposed, requiring no non-empty (k+1)-CTs in the dual network; (4) three algorithms based on strategies of up-down, bottom-up and binary search are proposed to find the MCTs. Extensive experiments conducted on real and synthetic large dual networks demonstrate the efficiency and effectiveness of our approaches.