Research And Application Of Influential Cohesive Subgraph Discovery Algorithm In Large Weighted Networks

Most real networks have the nature of sparse global and cohesive local structure.These local cohesive subgraphs are often the key to the networks,such as communities in social networks,functional clusters in biological neural networks and congestionprone nodes in road traffic networks.Therefore,finding influential cohesive subgraphs in large-scale weighted networks has become a hot research problem in the field of graph data management and mining,and how to effectively model and efficiently discover dense subgraphs in networks has attracted a lot of attention from researchers.In this paper,we study the problem of dense subgraph discovery in single/dual networks and give the corresponding algorithm design and specific application cases.First,the problem of dense subgraph discovery in single networks is studied.In this paper,we propose a new model local 6)-influential community(6)-LIC)based on the concept of 6)-core,specifically,the weight of a node in 6)-LIC is determined by the weight of the incident edge in the local subgraph in which it is located.For this model,the top- 6)-LICs mining problem is proposed,which aims to discover the top- 6)-LIC subgraphs with the highest influence.To solve the problem,an exact depth-first search algorithm Exact-LIC is first designed,which uses four pruning rules to enumerate top- 6)-LICs exactly.to further speed up the problem,an efficient greedy method is proposed to find approximate subgraphs based on a heuristic strategy.Comprehensive experimental results on several large networks demonstrate the effectiveness and efficiency of the model and method.Second,the problem of dense subgraph discovery in bipartite networks is investigated.A binational network is represented as two complementary single networks that contain the same set of vertices but different sets of edges,where one graph represents the physical relationship between vertices,which is called the physical graph,and the other graph represents the conceptual relationship between nodes,which is called the conceptual graph.Based on the bipartite network model and combined with the k-truss concept,this paper proposes a dense subgraph of influence defined according to the minimum edge weights,namely the 6)-influential connected truss(6)-ICT).For this model,the exact algorithms Exact-Gk ICT and Exact-Lk ICT based on global enumeration deletion and local subgraph expansion are proposed for discovering the 6)-ICT subgraphs with maximum influence for top-.Finally,the efficiency and effectiveness of the algorithms are verified by extensive experiments on real datasets.