Discovering Temporal Communities from Social Network Documents
Published 1 October 2007
Ding Zhou, Isaac G. Councill, Hongyuan Zha, C. Lee Giles
Citations74
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 proposes to discover the temporal communities by threading the statically derived communities in different time periods using a new constrained partitioning algorithm, which partitions graphs based on topology as well as prior information regarding vertex membership.
Abstract
This paper studies the discovery of communities from social network documents produced over time, addressing the discovery of temporal trends in community memberships. We first formulate static community discovery at a single time period as a tripartite graph partitioning problem. Then we propose to discover the temporal communities by threading the statically derived communities in different time periods using a new constrained partitioning algorithm, which partitions graphs based on topology as well as prior information regarding vertex membership. We evaluate the proposed approach on synthetic datasets and a real-world dataset prepared from the CiteSeer.
Keywords
Computer ScienceSocial SciencesPhysics and Astronomy
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
Social network analysis methods and applications
18,142 Citations2007Stanley Wasserman, Katherine Faust
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
Mining the network value of customers
2,868 Citations2001Pedro Domingos, Matt Richardson
It is proposed to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively, taking advantage of the availability of large relevant databases.
Group formation in large social networks
1,820 Citations2006Lars Bäckström, D.P. Huttenlocher +2 more
It is found that the propensity of individuals to join communities, and of communities to grow rapidly, depends in subtle ways on the underlying network structure, and decision-tree techniques are used to identify the most significant structural determinants of these properties.
SIAM Journal on Matrix Analysis and ApplicationsPartitioning Sparse Matrices with Eigenvectors of Graphs
1,692 Citations1990Alex Pothen, Horst D. Simon +1 more
It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph, which can be used to compute good separators in grid graphs.
Uncertainty in Artificial IntelligenceThe author-topic model for authors and documents
1,313 Citations2004Michal Rosen‐Zvi, Thomas Griffiths +2 more
Information diffusion through blogspace
1,045 Citations2004Daniel Gruhl, R. Guha +2 more
A macroscopic characterization of topic propagation through the authors' corpus is presented, formalizing the notion of long-running "chatter" topics consisting recursively of "spike" topics generated by outside world events, or more rarely, by resonances within the community.
Information-theoretic co-clustering
998 Citations2003Inderjit S. Dhillon, Subramanyam Mallela +1 more
This work presents an innovative co-clustering algorithm that monotonically increases the preserved mutual information by intertwining both the row and column clusterings at all stages and demonstrates that the algorithm works well in practice, especially in the presence of sparsity and high-dimensionality.
ACM SIGKDD Explorations NewsletterInformation diffusion through blogspace
951 Citations2004Daniel Gruhl, David Liben‐Nowell +2 more
A macroscopic characterization of topic propagation through the authors' corpus, formalizing the notion of long-running "chatter" topics consisting recursively of "spike" topics generated by outside world events, or more rarely, by resonances within the community.
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.
Research Commons (University of Waikato)Domain-specific keyphrase extraction
623 Citations1999Eibe Frank, Gordon W. Paynter +3 more
This paper shows that a simple procedure for keyphrase extraction based on the naive Bayes learning scheme performs comparably to the state of the art, and explains how this procedure's performance can be boosted by automatically tailoring the extraction process to the particular document collection at hand.
Spectral Relaxation for K-means Clustering
561 Citations2001Hongyuan Zha, Xiaofeng He +3 more
It is shown that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by Computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition ofThe eigenvector matrix.
Communities and TechnologiesEmail as Spectroscopy: Automated Discovery of Community Structure within Organizations
429 Citations2003Joshua R. Tyler, Dennis M. Wilkinson +1 more
The Information SocietyE-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations
330 Citations2005Joshua R. Tyler, Dennis M. Wilkinson +1 more
A betweenness centrality algorithm is used that can rapidly find communities within a graph representing information flows and is effective at identifying true communities, both formal and informal, within these scale-free graphs.
Bipartite graph partitioning and data clustering
285 Citations2001Hongyuan Zha, Xiaofeng He +3 more
A new data clustering method based on partitioning the underlying bipartite graph, which shows that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition of the associated edge weight matrix of the bipartites graph.
Probabilistic models for discovering e-communities
239 Citations2006Ding Zhou, Eren Manavoglu +3 more
Experimental studies on Enron email corpus show that the proposed generative Bayesian models for semantic community discovery in SNs successfully detects the communities of individuals and in addition provides semantic topic descriptions of these communities.
Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering
130 Citations2005Bin Gao, Tie‐Yan Liu +3 more
The concept of consistent bipartite graph co-partitioning is proposed, and an algorithm based on semi-definite programming (SDP) for efficient computation of the clustering results is developed.
Document clustering with prior knowledge
128 Citations2006Xiang Ji, Wei Xu
This work proposes to incorporate prior knowledge of cluster membership for document cluster analysis and develops a novel semi-supervised document clustering model that reveals remarkable performance improvements with very limited training samples, and is a very effective semi- supervised classification tool.
Mining scale-free networks using geodesic clustering
79 Citations2004Andrew Wu, Michael Garland +1 more
A new model for understanding scale-free networks based on multilevel geodesic approximation, using a new data structure called a multileVEL mesh is presented, and a new kind of graph clustering is proposed for data reduction of very large graph systems such as social, biological, or electronic networks.
Clustering spatial data using random walks
76 Citations2001David Harel, Yehuda Koren
Stochastic link and group detection
72 Citations2002Jeremy Kubica, Andrew Moore +2 more
A probabilistic model of link generation based on membership in groups is proposed that considers both observed link evidence and demographic information about the entities and shows several heuristics that make the search tractable.
Bipartite graph partitioning and data clustering
63 Citations2001Hongyuan Zha, Xiaofeng He +3 more
A Tutorial on Spectral Clustering
40 Citations2004Chris Ding
After overexpression of GmPHT4;10 gene in Arabidopsis thaliana, more phosphate and proline were accumulated in chloroplasts and catalase activity was increased, thus improving photosynthesis and drought resistance of plants.