Ranking-based clustering of heterogeneous information networks with star network schema
Published 28 June 2009
Yizhou Sun, Yintao Yu, Jiawei Han
Citations530
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper studies clustering of multi-typed heterogeneous networks with a star network schema and proposes a novel algorithm, NetClus, that utilizes links across multityped objects to generate high-quality net-clusters and generates informative clusters.
Abstract
A heterogeneous information network is an information network
Keywords
Computer SciencePhysics and Astronomy
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Statistics and ComputingA tutorial on spectral clustering
10,269 Citations2007Ulrike von Luxburg
This tutorial describes different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches.
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
Physical Review LettersAssortative Mixing in Networks
4,980 Citations2002M. E. J. Newman
This work proposes a model of an assortatively mixed network and finds that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.
Proceedings of the National Academy of SciencesThe structure of scientific collaboration networks
4,502 Citations2001M. E. J. Newman
It is shown that these collaboration networks form "small worlds," in which randomly chosen pairs of scientists are typically separated by only a short path of intermediate acquaintances.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
arXiv (Cornell University)Probabilistic Latent Semantic Analysis
2,092 Citations2013Thomas Hofmann
This work proposes a widely applicable generalization of maximum likelihood model fitting by tempered EM, based on a mixture decomposition derived from a latent class model which results in a more principled approach which has a solid foundation in statistics.
SimRank
1,938 Citations2002Glen Jeh, Jennifer Widom
A complementary approach, applicable in any domain with object-to-object relationships, that measures similarity of the structural context in which objects occur, based on their relationships with other objects is proposed.
ACM Transactions on Information SystemsA study of smoothing methods for language models applied to information retrieval
1,212 Citations2004ChengXiang Zhai, John Lafferty
Evaluation on five different databases and four types of queries indicates that the two-stage smoothing method with the proposed parameter estimation methods consistently gives retrieval performance that is close to or better than the best results achieved using a single smoothing methods and exhaustive parameter search on the test data.
Normalized cuts and image segmentation
863 Citations2002Jianbo Shi, Jitendra Malik
This work treats image segmentation as a graph partitioning problem and proposes a novel global criterion, the normalized cut, for segmenting the graph, which measures both the total dissimilarity between the different groups as well as the total similarity within the groups.
A min-max cut algorithm for graph partitioning and data clustering
828 Citations2002Chris Ding, Xiaofeng He +3 more
This paper proposes a new algorithm for graph partitioning with an objective function that follows the min-max clustering principle, and demonstrates that a linearized search order based on linkage differential is better than that based on the Fiedler vector, providing another effective partitioning method.
SCAN
821 Citations2007Xiaowei Xu, Nurcan Yuruk +2 more
A novel algorithm called SCAN (Structural Clustering Algorithm for Networks), which detects clusters, hubs and outliers in networks and clusters vertices based on a structural similarity measure is proposed.
Probabilistic author-topic models for information discovery
581 Citations2004Mark Steyvers, Padhraic Smyth +2 more
The methodology is applied to a large corpus of 160,000 abstracts and 85,000 authors from the well-known CiteSeer digital library, and a model with 300 topics is learned using a Markov chain Monte Carlo algorithm.
Efficient aggregation for graph summarization
438 Citations2008Yuanyuan Tian, Richard A. Hankins +1 more
This paper introduces two database-style operations to summarize graphs, called SNAP and k-SNAP, that allow users to control the resolutions of summaries and provides the "drill-down" and "roll-up" abilities to navigate through summaries with different resolutions.
A Spectral Clustering Approach To Finding Communities in Graphs
399 Citations2005Scott R. White, Padhraic Smyth
This paper shows how optimizing the Q function can be reformulated as a spectral relaxation problem and proposes two new spectral clustering algorithms that seek to maximize Q and indicates that the new algorithms are efficient and effective at finding both good clusterings and the appropriate number of clusters across a variety of real-world graph data sets.
RankClus
378 Citations2009Yizhou Sun, Jiawei Han +4 more
This paper addresses the problem of generating clusters for a specified type of objects, as well as ranking information for all types of objects based on these clusters in a multi-typed information network, and proposes a novel clustering framework called RankClus that directly generates clusters integrated with ranking.
A cross-collection mixture model for comparative text mining
275 Citations2004ChengXiang Zhai, Atulya Velivelli +1 more
A generative probabilistic mixture model is proposed for comparative text mining that simultaneously performs cross-collection clustering and within- collection clustering, and can be applied to an arbitrary set of comparable text collections.
Object-level ranking
266 Citations2005Zaiqing Nie, Yuanzhi Zhang +2 more
The experimental results show that PopRank can achieve significantly better ranking results than naively applying PageRank on the object graph, and the proposed efficient approaches to automatically decide these factors are proposed.
Spectral clustering for multi-type relational data
253 Citations2006Bo Long, Zhongfei Zhang +2 more
A general model, the collective factorization on related matrices, is proposed for multi-type relational data clustering and a novel algorithm is derived, the spectral relational clustering, to cluster multi- type interrelated data objects simultaneously.
Multi-way Clustering on Relation Graphs
125 Citations2007Arindam Banerjee, Sugato Basu +1 more
This paper proposes a principled multi-way clustering framework for relational data, wherein different types of entities are simultaneously clustered based not only on their intrinsic attribute values, but also on the multiple relations between the entities.
Multi-way distributional clustering via pairwise interactions
104 Citations2005Ron Bekkerman, Ran El‐Yaniv +1 more
An extensive empirical study of two-way, three-way and four-way applications of the MDC scheme using six real-world datasets including the 20 News-groups and the Enron email collection shows that the algorithms consistently and significantly outperform previous state-of-the-art information theoretic clustering algorithms.
A general optimization framework for smoothing language models on graph structures
64 Citations2008Qiaozhu Mei, Duo Zhang +1 more
This paper proposes a general and unified optimization framework for smoothing language models on graph structures that provides a unified formulation of the existing smoothing heuristics, and serves as a road map for systematically exploring smoothing methods for language models.
CSV
62 Citations2008Nan Wang, Srinivasan Parthasarathy +2 more
This article proposes an approximate algorithm, to mine and visualize cohesive subgraphs (dense sub components) within a large graph, which relies on a novel mapping strategy that maps edges and nodes to a multi-dimensional space wherein dense areas in the mapped space correspond to cohesive sub graphs.