Identifying Relevant Subgraphs in Large Networks

摘要：

　　Structural relationships between objects are used to model as graphs in many applications.In this paper,we study the problem of identifying relevant subgraphs in large networks.Relevant subgraphs in large networks contain network elements which are maintained by network administrators.We formalize the problem and propose a framework consisting of two major phases.The relevance scores of all vertex pairs are computed in the offline phase,while relevant subgraphs are identified in the online phase.We analyze the relevance score measure carefully and design an efficient algorithm for relevant subgraph identification by repeatedly expanding candidate subgraphs and merging overlapping ones.Our experiments based on real data sets show that our relevant subgraphs are of high quality and can be found efficiently,which are useful for network administrators during network operation and maintenance.

作者: Zheng Liu Shuting Guo Tao Li Wenyan Chen

作者单位: School of Computer Science and Technology,Nanjing University of Posts and Telecommunications,Nanjing,China

会议类型: 国际会议

会议名称: International Asia-Pacific Web Conference(第18届国际亚太互联网大会)

会议地点: 苏州

会议语种:英文

页码: 139-151

在线出版日期: 2016-09-23（万方平台首次上网日期，不代表论文的发表时间）