Searching the Informative Subgraph Based on the PeakGraph Model
Huilin Liu, Chen Chen, Junchang Xin, Liyuan Zhang · The Computer Journal · 2016
In the area of social network, bioinformatics, e-commerce and so on, the graph model is widely used to present the certain objects and the relations among them. Taking such graph model as the source data, it is significant to extract the compact informative subgraph which can best explain how the given query points are connected. Existing work considers only the connection between individual objects and the returned subgraph is unfavorable when the given query points are far distant each other in the initial graph. In the paper, we will first simplify and present the initial graph by the PeakGraph model in which the graph nodes are divided into different groups based on the density of linkages. Based on the PeakGraph model, we further extract the informative subgraph by two steps, namely local search and global search. In the former step, the local optimal subgraph is extracted for each group; in the latter step, we connect these local optimal subgraphs by some heuristic rules. Our experiments show that our algorithm achieves good performance in both accuracy and efficiency for all kinds of queries.