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

research-article

Component Detection in Directed Networks

Authors:

Srinivasan ParthasarathyAuthors Info & Claims

CIKM '14: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management

Pages 1729 - 1738

https://doi.org/10.1145/2661829.2662074

Published: 03 November 2014 Publication History

Abstract

Community detection has been one of the fundamental problems in network analysis. Results from community detection (for example, grouping of products by latent category) can also serve as information nuggets to other business applications, such as product recommendation or taxonomy building. Because several real networks are naturally directed, e.g. World Wide Web, some recent studies proposed algorithms for detecting various types of communities in a directed network. However, few of them considered that nodes play two different roles, source and terminal, in a directed network.

In this paper, we adopt a novel concept of communities, directional community, and propose a new algorithm based on Markov Clustering to detect directional communities. We then first compare our algorithm, Dual R-MCL, on synthetic networks with two recent algorithms also designed for detecting directional communities. We show that Dual R-MCL can detect directional communities with significantly higher accuracy and 3x to 25x faster than the two other algorithms. Second, we compare a set of directed network community detection algorithms on a one-day Twitter interaction network and demonstrate that Dual R-MCL can generate clusters more correctly matched to hashtags. Finally, we exhibit our algorithm's capacity to identify directional communities from product description networks, where nodes are otherwise not directly connected.

Results indicate that directional communities exist in real networks, and Dual R-MCL can effectively detect these directional communities. We believe it will enable the discovery of interesting components in a diverse types of networks where existing methods cannot, and it manifests strong application values.

References

[1]

Y. Y. Ahn, J. P. Bagrow, and S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466(7307):761--764, 2010.

[2]

S. Asur, D. Ucar, and S. Parthasarathy. An ensemble framework for clustering protein--protein interaction networks. Bioinformatics, 23(13):i29--i40, 2007.

Digital Library

[3]

M. Benzi, E. Estrada, and C. Klymko. Ranking hubs and authorities using matrix functions. Linear Algebra and its Applications, 2012.

[4]

S. Brohee and J. V. Helden. Evaluation of clustering algorithms for protein-protein interaction networks. BMC bioinformatics, 7(1):488, 2006.

[5]

F. Chen, A. J. Mackey, C. J. Stoeckert, and D. S. Roos. Orthomcl-db: querying a comprehensive multi-species collection of ortholog groups. Nucleic acids research, 34(suppl 1):D363--D368, 2006.

[6]

M. Coscia, F. Giannotti, and D. Pedreschi. A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining, 4(5):512--546, 2011.

Digital Library

[7]

L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008, 2005.

[8]

S. V. Dongen. Graph clustering by flow simulation. PhD thesis, University of Utrecht, 2000.

[9]

S. Fortunato. Community detection in graphs. Physics Reports, 486(3--5):75--174, 2010.

[10]

R. Guimerà, M. Sales-Pardo, and L. A. N. Amaral. Module identification in bipartite and directed networks. Physical Review E, 76(3):036102, 2007.

[11]

M. A. Jaro. Advances in record-linkage methodology as applied to matching the 1985 census of tampa, florida. Journal of the American Statistical Association, 84(406):414--420, 1989.

[12]

S. Kim and T. Shi. Scalable spectral algorithms for community detection in directed networks. arXiv preprint arXiv:1211.6807, 2012.

[13]

J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The web as a graph: Measurements, models, and methods. In Computing and combinatorics, pages 1--17. Springer, 1999.

Digital Library

[14]

A. Lancichinetti and S. Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1):016118, 2009.

[15]

A. Lancichinetti, S. Fortunato, and J. Kertész. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3):033015, 2009.

[16]

E. A. Leicht and M. E. Newman. Community structure in directed networks. Physical review letters, 100(11):118703, 2008.

[17]

X. Li, M. Wu, C. K. Kwoh, and S. K. Ng. Computational approaches for detecting protein complexes from protein interaction networks: a survey. BMC genomics, 11(Suppl 1):S3, 2010.

[18]

F. D. Malliaros and M. Vazirgiannis. Clustering and community detection in directed networks: A survey. Physics Reports, 2013.

[19]

M. Meil\ua and W. Pentney. Clustering by weighted cuts in directed graphs. In SIAM Conference on Data Mining (SDM). SIAM, 2007.

[20]

V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri. Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment, (03):03024, 2009.

[21]

G. Palla, I. J. Farkas, P. Pollner, I. Derenyi, and T. Vicsek. Directed network modules. New Journal of Physics, 9(6):186, 2007.

[22]

A. Ritter, S. Clark, Mausam, and O. Etzioni. Named entity recognition in tweets: An experimental study. In EMNLP, 2011.

Digital Library

[23]

K. Rohe and B. Yu. Co-clustering for directed graphs; the stochastic co-blockmodel and a spectral algorithm. arXiv preprint arXiv:1204.2296, 2012.

[24]

M. Rosvall, D. Axelsson, and C. T. Bergstrom. The map equation. The European Physical Journal Special Topics, 178(1):13--23, 2009.

[25]

M. Rosvall and C. T. Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4):1118--1123, 2008.

[26]

V. Satuluri and S. Parthasarathy. Scalable graph clustering using stochastic flows: applications to community discovery. In Proceedings of SIGKDD, pages 737--746. ACM, 2009.

Digital Library

[27]

V. Satuluri and S. Parthasarathy. Symmetrizations for clustering directed graphs. In Proceedings of the 14th International Conference on Extending Database Technology, pages 343--354, 2011.

Digital Library

[28]

V. Satuluri, S. Parthasarathy, and Y. Ruan. Local graph sparsification for scalable clustering. In Proceedings of the 2011 international conference on Management of data, pages 721--732, 2011.

Digital Library

[29]

V. Satuluri, S. Parthasarathy, and D. Ucar. Markov clustering of protein interaction networks with improved balance and scalability. In Proceedings of ACM-BCB, pages 247--256, 2010.

Digital Library

[30]

Y. Shih and S. Parthasarathy. Identifying functional modules in interaction networks through overlapping markov clustering. Bioinformatics, 28(18):i473--i479, 2012.

Digital Library

[31]

L. Wang, T. Lou, J. Tang, and J. E. Hopcroft. Detecting community kernels in large social networks. In ICDM, pages 784--793, 2011.

Digital Library

[32]

J. Yang and J. Leskovec. Overlapping community detection at scale: A nonnegative matrix factorization approach. In Proceedings of the sixth ACM international conference on Web search and data mining, pages 587--596, 2013.

Digital Library

[33]

T. Yang, Y. Chi, S. Zhu, Y. Gong, and R. Jin. Directed network community detection: A popularity and productivity link model. In SDM, pages 742--753, 2010.

[34]

D. Zhou, B. Schölkopf, and T. Hofmann. Semi-supervised learning on directed graphs. 2005.

[35]

H. Zou and T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301--320, 2005.

Cited By

Wang ZWang CLi XGao CLi XZhu J(2022)Evolutionary Markov Dynamics for Network Community DetectionIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299704334:3(1206-1220)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TKDE.2020.2997043
Gao CLiang MLi XZhang ZWang ZZhou Z(2018)Network Community Detection Based on the Physarum-Inspired Computational FrameworkIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2016.263882415:6(1916-1928)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1109/TCBB.2016.2638824

Index Terms

Component Detection in Directed Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Regularized asymmetric nonnegative matrix factorization for clustering in directed networks
Highlights
- Nonnegative matrix factorization based clustering algorithm is proposed for directed networks.
Abstract
In network analysis, clustering is a key task of dividing a network into logical and meaningful groupings of components. There are various methods to cluster nodes in undirected networks, however, little is known about clustering in ...
Detecting Overlapping Communities in Directed Networks Based on Link Similarity
ICCIS '13: Proceedings of the 2013 International Conference on Computational and Information Sciences

Identifying overlapping communities in networks has attracted increasing attention recently, but the most common approach to this problem has been to ignore the edge direction and apply the methods in undirected networks. In this paper, an overlapping ...
Directed association network analysis on the Standard and Poor’s 500 Index
Abstract
In this paper, we study the association between the core American listed companies by analysing the stock data of the Standard and Poor’s 500 Index. During the network analysis, we use a new correlation coefficient (Chatterjee in J Am Stat Assoc ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '14: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management

November 2014

2152 pages

ISBN:9781450325981

DOI:10.1145/2661829

General Chairs:
Jianzhong Li
Harbin Inst. of Technology
,
X. Sean Wang
Fudan University
,
Program Chairs:
Minos Garofalakis
Technical University of Crete, Greece
,
Ian Soboroff
National Institute of Standards, USA
,
Torsten Suel
New York University, USA
,
Min Wang
Google Research, USA

Copyright © 2014.

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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CIKM '14

Sponsor:

CIKM '14: 2014 ACM Conference on Information and Knowledge Management

November 3 - 7, 2014

Shanghai, China

Acceptance Rates

CIKM '14 Paper Acceptance Rate 175 of 838 submissions, 21%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
216
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZWang CLi XGao CLi XZhu J(2022)Evolutionary Markov Dynamics for Network Community DetectionIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299704334:3(1206-1220)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TKDE.2020.2997043
Gao CLiang MLi XZhang ZWang ZZhou Z(2018)Network Community Detection Based on the Physarum-Inspired Computational FrameworkIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2016.263882415:6(1916-1928)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1109/TCBB.2016.2638824

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.

Media

Figures

Other

Tables

View Table of Contents