More Web Proxy on the site http://driver.im/

research-article

Facetnet: a framework for analyzing communities and their evolutions in dynamic networks

Authors:

Belle L. TsengAuthors Info & Claims

WWW '08: Proceedings of the 17th international conference on World Wide Web

Pages 685 - 694

https://doi.org/10.1145/1367497.1367590

Published: 21 April 2008 Publication History

Abstract

We discover communities from social network data, and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified process. In this novel framework, communities not only generate evolutions, they also are regularized by the temporal smoothness of evolutions. As a result, this framework will discover communities that jointly maximize the fit to the observed data and the temporal evolution. Our approach relies on formulating the problem in terms of non-negative matrix factorization, where communities and their evolutions are factorized in a unified way. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.

References

[1]

S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In Proc. of the 13th ACM SIGKDD Conference, 2007.

Digital Library

[2]

D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. In Proc. of the 12th ACM SIGKDD Conference, 2006.

Digital Library

[3]

Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. In Proc. of the 13th ACM SIGKDD Conference, 2007.

Digital Library

[4]

F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.

[5]

S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proc. of the 10th ACM SIGKDD Conference, 2004.

Digital Library

[6]

G. Flake, S. Lawrence, and C. Giles. Efficient identification of web communities. In Proc. of the 6th ACM SIGKDD Conference, 2000.

Digital Library

[7]

J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. of the ACM, 46(5), 1999.

Digital Library

[8]

R. Kumar, J. Novak, P. Raghavan, and A. Tomkins. On the bursty evolution of blogspace. In Proc. of the 12th WWW Conference, 2003.

Digital Library

[9]

R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In Proc. of the 12th ACM SIGKDD Conference, 2006.

Digital Library

[10]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proc. of the 11th ACM SIGKDD Conference, 2005.

Digital Library

[11]

Y. Lin, H. Sundaram, Y. Chi, J. Tatemura, and B. L. Tseng. Blog community discovery and evolution based on mutual awareness expansion. In Proc. of the Int. Conf. on Web Intelligence, 2007.

Digital Library

[12]

Q. Mei and C. Zhai. Discovering evolutionary theme patterns from text: an exploration of temporal text mining. In Proc. of the 11th ACM SIGKDD Conference, 2005.

Digital Library

[13]

M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 2004.

[14]

H. Ning, W. Xu, Y. Chi, Y. Gong, and T. Huang. Incremental spectral clustering with application to monitoring of evolving blog communities. In SIAM Int. Conf. on Data Mining, 2007.

[15]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. In Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.

[16]

G. Palla, A.-L. Barabasi, and T. Vicsek. Quantifying social group evolution. Nature, 446, 2007.

[17]

P. Sarkar and A. W. Moore. Dynamic social network analysis using latent space models. SIGKDD Explor. Newsl., 7(2), 2005.

Digital Library

[18]

J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8), 2000.

Digital Library

[19]

M. Spiliopoulou, I. Ntoutsi, Y. Theodoridis, and R. Schult. Monic: modeling and monitoring cluster transitions. In Proc. of the 12th ACM SIGKDD Conference, 2006.

Digital Library

[20]

J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu. GraphScope: parameter-free mining of large time-evolving graphs. In Proc. of the 13th ACM SIGKDD Conference, 2007.

Digital Library

[21]

M. Toyoda and M. Kitsuregawa. Extracting evolution of web communities from a series of web archives. In HYPERTEXT '03: Proc. of the 14th ACM conference on hypertext and hypermedia, 2003.

Digital Library

[22]

S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.

[23]

S. White and P. Smyth. A spectral clustering approach to finding communities in graph. In SDM, 2005.

[24]

K. Yu, S. Yu, and V. Tresp. Soft clustering on graphs. In NIPS, 2005.

[25]

H. Zha, X. He, C. H. Q. Ding, M. Gu, and H. D. Simon. Spectral relaxation for k-means clustering. In NIPS, 2001.

Cited By

Zhang LQin CYang HXiong ZCao RCheng F(2025)A Diversified Population Migration-Based Multiobjective Evolutionary Algorithm for Dynamic Community DetectionIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2024.34515669:1(145-159)Online publication date: Feb-2025
https://doi.org/10.1109/TETCI.2024.3451566
Amar MBouguessa MDiallo A(2025)MLCDG: Multi-Level Contrastive Graph Clustering in Dynamic GraphsSocial Networks Analysis and Mining10.1007/978-3-031-78548-1_16(197-210)Online publication date: 24-Jan-2025
https://doi.org/10.1007/978-3-031-78548-1_16
Dabke DDorabiala O(2024)Vertex clustering in diverse dynamic networksPLOS Complex Systems10.1371/journal.pcsy.00000231:4(e0000023)Online publication date: 5-Dec-2024
https://doi.org/10.1371/journal.pcsy.0000023
Show More Cited By

Index Terms

Facetnet: a framework for analyzing communities and their evolutions in dynamic networks
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
      1. Document filtering
      2. Information extraction
  2. Information systems applications
    1. Data mining

Recommendations

Analyzing communities and their evolutions in dynamic social networks

We discover communities from social network data and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over ...
Maximizing modularity intensity for community partition and evolution

Most previous studies of community partition have often focused on the network topology, the topology and link weights are in fact closely associated with each other for community formation in complex networks. This paper proposes a function-modularity ...
Characterizing the Evolution of Communities on Reddit
SMSociety'20: International Conference on Social Media and Society

One of the most important structures in social networks is communities. Communities in social networks evolve over time. Understanding the evolution of communities is useful in many applications, such as building successful communities, maintaining the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '08: Proceedings of the 17th international conference on World Wide Web

April 2008

1326 pages

ISBN:9781605580852

DOI:10.1145/1367497

General Chairs:
Jinpeng Huai
Beihang University, China
,
Robin Chen
AT&T Labs, USA
,
Hsiao-Wuen Hon
Microsoft Research Asia, China
,
Yunhao Liu
HK University of Science and Technology, Hong Kong
,
Program Chairs:
Wei-Ying Ma
Microsoft Research Asia, China
,
Andrew Tomkins
Yahoo! Research, USA
,
Xiaodong Zhang
The Ohio State University, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 April 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '08

Sponsor:

ACM

WWW '08: The 17th International World Wide Web Conference

April 21 - 25, 2008

Beijing, China

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

288
Total Citations
View Citations
1,938
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)5

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LQin CYang HXiong ZCao RCheng F(2025)A Diversified Population Migration-Based Multiobjective Evolutionary Algorithm for Dynamic Community DetectionIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2024.34515669:1(145-159)Online publication date: Feb-2025
https://doi.org/10.1109/TETCI.2024.3451566
Amar MBouguessa MDiallo A(2025)MLCDG: Multi-Level Contrastive Graph Clustering in Dynamic GraphsSocial Networks Analysis and Mining10.1007/978-3-031-78548-1_16(197-210)Online publication date: 24-Jan-2025
https://doi.org/10.1007/978-3-031-78548-1_16
Dabke DDorabiala O(2024)Vertex clustering in diverse dynamic networksPLOS Complex Systems10.1371/journal.pcsy.00000231:4(e0000023)Online publication date: 5-Dec-2024
https://doi.org/10.1371/journal.pcsy.0000023
Richardson TKay TKeller LStroeymeyt N(2024)Pheromone relay networks in the honeybee: messenger workers distribute the queen’s fertility signal throughout the hiveBMC Biology10.1186/s12915-024-02083-w22:1Online publication date: 18-Dec-2024
https://doi.org/10.1186/s12915-024-02083-w
Agarwal PHu XSintos SYang J(2024)On Reporting Durable Patterns in Temporal Proximity GraphsProceedings of the ACM on Management of Data10.1145/36511442:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651144
Li HCao HFeng YLi XPei J(2024)Optimization of Graph Clustering Inspired by Dynamic Belief SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327454736:11(6773-6785)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2023.3274547
Ma HWu KWang HLiu J(2024)Higher Order Knowledge Transfer for Dynamic Community Detection With Great ChangesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325756328:1(90-104)Online publication date: Feb-2024
https://doi.org/10.1109/TEVC.2023.3257563
McGregor SUslu FSakar MKeller L(2024)Targeted worker removal reveals a lack of flexibility in brood transport specialisation with no compensatory gain in efficiencyScientific Reports10.1038/s41598-024-55244-w14:1Online publication date: 28-Feb-2024
https://doi.org/10.1038/s41598-024-55244-w
Bahadori SMirzaie MNooraei Abadeh M(2024)A multi-objective optimization approach for overlapping dynamic community detectionSoft Computing10.1007/s00500-024-09895-628:19(11323-11342)Online publication date: 24-Jul-2024
https://doi.org/10.1007/s00500-024-09895-6
Hu KZhang ZLi X(2024)Research on Dynamic Community Detection Method Based on Multi-dimensional Feature Information of Community NetworkTrends and Applications in Knowledge Discovery and Data Mining10.1007/978-981-97-2650-9_4(44-56)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-981-97-2650-9_4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten