Pienta Robert, Tamersoy Acar, Tong Hanghang, Chau Duen Horng
College of Computing, Georgia Institute of Technology, Atlanta, GA.
Department of Computer Science, Arizona Sate University, Phoenix, AZ.
Proc IEEE Int Conf Big Data. 2014 Oct;2014:585-590. doi: 10.1109/BigData.2014.7004278.
Given a large graph with millions of nodes and edges, say a social network where both its nodes and edges have multiple attributes (e.g., job titles, tie strengths), how to quickly find subgraphs of interest (e.g., a ring of businessmen with strong ties)? We present MAGE, a scalable, multicore subgraph matching approach that supports expressive queries over large, richly-attributed graphs. Our major contributions include: (1) MAGE supports graphs with both node and edge attributes (most existing approaches handle either one, but not both); (2) it supports expressive queries, allowing multiple attributes on an edge, wildcards as attribute values (i.e., match permissible values), and attributes with continuous values; and (3) it is scalable, supporting graphs with several hundred million edges. We demonstrate MAGE's effectiveness and scalability via extensive experiments on large real and synthetic graphs, such as a Google+ social network with edges.
给定一个包含数百万个节点和边的大型图，比如说一个社交网络，其中其节点和边都具有多个属性（例如，职位头衔、关系强度），如何快速找到感兴趣的子图（例如，由关系紧密的商人组成的环）？我们提出了MAGE，一种可扩展的多核子图匹配方法，它支持对大型、属性丰富的图进行表达性查询。我们的主要贡献包括：（1）MAGE支持具有节点和边属性的图（大多数现有方法只处理其中之一，而非两者）；（2）它支持表达性查询，允许边具有多个属性、通配符作为属性值（即匹配允许的值）以及具有连续值的属性；（3）它具有可扩展性，支持具有数亿条边的图。我们通过在大型真实和合成图上进行广泛实验，如具有[此处缺失边数量信息]条边的谷歌+社交网络，来证明MAGE的有效性和可扩展性。
