子图匹配中基于启发式策略的图分割算法
|
摘要
在大规模的子图匹配过程中,如果直接对原有数据图进行查询,那么所需要的内存和时间开销都是相当巨大的。而根据现实网络的特性,假定用户大多数查询都在社区范围内,如果通过图分割算法将数据图分成多个分区,如此可在不同的分区中同时进行匹配查询,可以极大提高查询效率。提出基于启发式策略的图分割算法(HSGSA),经实验证明,分割时间不会随着图规模的增大而急剧增加,对内存的消耗也不会显著增加,并且分割后进行匹配存在合理性。
In the large-scale subgraph matching process,if the original data graph is directly queried,the required memory and time overhead are quite large.According to the characteristics of the real network,it is assumed that most of the users' queries are within the community.If the data graph is divided into multiple partitions by the graph segmentation algorithm,matching queries can be performed simultaneously in different partitions,which can greatly improve the query efficiency.Proposes the graph segmentation algorithm based on heuristic strategy to prove that the segmentation time and required memory do not increase sharply with the increase of the scale of the graph,and the matching after segmentation is reasonable.
In the large-scale subgraph matching process,if the original data graph is directly queried,the required memory and time overhead are quite large.According to the characteristics of the real network,it is assumed that most of the users' queries are within the community.If the data graph is divided into multiple partitions by the graph segmentation algorithm,matching queries can be performed simultaneously in different partitions,which can greatly improve the query efficiency.Proposes the graph segmentation algorithm based on heuristic strategy to prove that the segmentation time and required memory do not increase sharply with the increase of the scale of the graph,and the matching after segmentation is reasonable.
引文
[1]Hein D-I O,Schwind D-W-I M,Konig W.Scale-Free Networks[J].Wirtschafts Informatick,2006,48(4):267-275.
[2]方滨兴.在线社交网络分析[M].北京:电子工业出版社,2014:24.
[3]Usha Nandini Raghavan,Reka Alert,Soundar Kumara.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[J].Physics Review E,76,036106,Sep.2007.
[4]Chuan Shi,Philio Yu,Zhengyu Yan,Yue Huang,Bai Wang.Comparison and Selection of Objective Functions in Multi-Objective Community detection.[J].Computational Intelligence,2013.
[5]Karypis G,Kumar V.A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering[J].Journal of Parallel and Distributed Computing,1998,48(1):71-95.
[6]ZhangS,Yang J,Jin W.SAPPER:Subgraph Indexing and Approximate Matching in Large Graphs[J].Proceedings of the VLDB Endowment,2010,3(1-2):1185-1194.
[7]R.Hanneman,M.Riddle.Introduction to Social Network Methods.http://faculty.ucr.edu/hanneman/,2005,36.
[8]D.Gibson,R.Kunmar,A.Tomkins.Discovering Large Dense Subgraphs in Massive Graphs[C].In VLDB'05:Proceedings of the 31st International Conference on Very Large Data Bases,p721-732.VLDB Endowment,2005.
[9]J.Hopcroft,O.Khan,B.Kulis,B.Selman.Natural Communities in Large Linked Networks[C].In KDD'03:Proceedings of the Ninth ACMSIGKDD International Conference on Knowledge Discovery and Data Mining,p541-546,New York,NY,USA,2003.
[2]方滨兴.在线社交网络分析[M].北京:电子工业出版社,2014:24.
[3]Usha Nandini Raghavan,Reka Alert,Soundar Kumara.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[J].Physics Review E,76,036106,Sep.2007.
[4]Chuan Shi,Philio Yu,Zhengyu Yan,Yue Huang,Bai Wang.Comparison and Selection of Objective Functions in Multi-Objective Community detection.[J].Computational Intelligence,2013.
[5]Karypis G,Kumar V.A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering[J].Journal of Parallel and Distributed Computing,1998,48(1):71-95.
[6]ZhangS,Yang J,Jin W.SAPPER:Subgraph Indexing and Approximate Matching in Large Graphs[J].Proceedings of the VLDB Endowment,2010,3(1-2):1185-1194.
[7]R.Hanneman,M.Riddle.Introduction to Social Network Methods.http://faculty.ucr.edu/hanneman/,2005,36.
[8]D.Gibson,R.Kunmar,A.Tomkins.Discovering Large Dense Subgraphs in Massive Graphs[C].In VLDB'05:Proceedings of the 31st International Conference on Very Large Data Bases,p721-732.VLDB Endowment,2005.
[9]J.Hopcroft,O.Khan,B.Kulis,B.Selman.Natural Communities in Large Linked Networks[C].In KDD'03:Proceedings of the Ninth ACMSIGKDD International Conference on Knowledge Discovery and Data Mining,p541-546,New York,NY,USA,2003.