Discovering informative connection subgraphs in multi-relational graphs
- 1 December 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGKDD Explorations Newsletter
- Vol. 7 (2), 56-63
- https://doi.org/10.1145/1117454.1117462
Abstract
Discovering patterns in graphs has long been an area of interest. In most approaches to such pattern discovery either quantitative anomalies, frequency of substructure or maximum flow is used to measure the interestingness of a pattern. In this paper we introduce heuristics that guide a subgraph discovery algorithm away from banal paths towards more "informative" ones. Given an RDF graph a user might pose a question of the form: "What are the most relevant ways in which entity X is related to entity Y?" the response to which is a subgraph connecting X to Y. We use our heuristics to discover informative subgraphs within RDF graphs. Our heuristics are based on weighting mechanisms derived from edge semantics suggested by the RDF schema. We present an analysis of the quality of the subgraphs generated with respect to path ranking metrics. We then conclude presenting intuitions about which of our weighting schemes and heuristics produce higher quality subgraphs.Keywords
This publication has 12 references indexed in Scilit:
- Mining hidden community in heterogeneous social networksPublished by Association for Computing Machinery (ACM) ,2005
- Ranking Complex Relationships on the Semantic WebIEEE Internet Computing, 2005
- SemRankPublished by Association for Computing Machinery (ACM) ,2005
- CloseGraphPublished by Association for Computing Machinery (ACM) ,2003
- Semantic searchPublished by Association for Computing Machinery (ACM) ,2003
- Ρ-QueriesPublished by Association for Computing Machinery (ACM) ,2003
- Self-organization and identification of Web communitiesComputer, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Inferring Web communities from link topologyPublished by Association for Computing Machinery (ACM) ,1998