Influential Cohesive Subgraph Discovery Algorithm in Dual Networks

Dual networks are composed of physical graph and concept graph. The physical graph and concept graph share the same set of vertices but have different sets of edges. The edges of physical graph represent the real relationship between vertices, while those of concept graph represent the similarity between vertices, usually obtained by computation. Recently, discovering cohesive subgraphs from dual networks, i.e., the subgraphs that connected in physical graph, while cohesive in concept graphs, has attracted extensive attention of researchers. The subgraphs have been widely used in many real scenarios such as seminar preparation, product recommendation and disease causing gene discovery. Yet, few existing studies have considered the influence of cohesive subgraphs in dual networks. To this end, in this paper: 1) An influential cohesive subgraph based on the minimum edge weight, i.e., influential k-connected truss (k-ICT) subgraph model is proposed. The k-ICT subgraph model can effectively characterize the importance of subgraphs in dual networks and is robust to low-influence edges. 2) As it proves finding the k-ICT with the largest influence is NP-hard, a CT index based on equivalence class partition of edges in the concept graph is proposed. By exploiting the summary graph of the index, candidate subgraphs containing all k-ICTs can be quickly found for different k values. 3) Exact- \mathrmG kICT and Exact-LkICT algorithms are proposed, respectively, based on the global enumeration deletion and local subgraph expansion, to identify the top-r k-ICTs with the largest influences. Extensive experiments conducted on real datasets verify the efficiency and effectiveness of our approaches.