Inferring Higher-Order Structure Statistics of Large Networks from Sampled Edges

作     者：Wang, Pinghui Qi, Yiyan Lui, John C. S. Towsley, Don Zhao, Junzhou Tao, Jing 

作者机构：Xi An Jiao Tong Univ MOE Key Lab Intelligent Networks & Network Secur POB 108828 Xianning West Rd Xian 710049 Shaanxi Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA 

出 版 物：《IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING》 (IEEE知识与数据工程汇刊)

年 卷 期：2019年第31卷第1期

页      面：61-74页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [U1301254, 61603290, 61602371] Ministry of Education & China Mobile Research Fund [MCM20160311] Natural Science Foundation of JiangSu Province [SBK2014021758] 111 International Collaboration Program of China Prospective Joint Research of Industry-Academia-Research Joint Innovation Funding of Jiangsu Province [BY2014074] Shenzhen Basic Research Grant [JCYJ20160229195940462] China Postdoctoral Science Foundation [2015M582663] Natural Science Basic Research Plan in Shaanxi Province of China [2016JQ6034] Army Research Office [W911NF-12-1-0385] ARL [W911NF-09-2-0053] 

主　　题：Graphlet motif subgraph sampling graph mining 

摘      要：Recently exploring locally connected subgraphs (also known as motifs or graphlets) of complex networks attracts a lot of attention. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring usually use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we call a RESampled graph. Clearly, a RESampled graph s motif statistics may be quite different from those of the original graph. To resolve this, we propose a framework Minfer, which takes the given RESampled graph and accurately infers the underlying graph s motif statistics. Experiments using large scale datasets show the accuracy and efficiency of our method.