The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
Dense Subgraph Extraction with Application to Community Detection
Abstract
This paper presents a method for identifying a set of dense subgraphs of a given sparse graph. Within the main applications of this “dense subgraph problem,” the dense subgraphs are interpreted as communities, as in, e.g., social networks. The problem of identifying dense subgraphs helps analyze graph structures and complex networks and it is known to be challenging. It bears some similarities with the problem of reordering/blocking matrices in sparse matrix techniques. We exploit this link and adapt the idea of recognizing matrix column similarities, in order to compute a partial clustering of the vertices in a graph, where each cluster represents a dense subgraph. In contrast to existing subgraph extraction techniques which are based on a complete clustering of the graph nodes, the proposed algorithm takes into account the fact that not every participating node in the network needs to belong to a community. Another advantage is that the method does not require to specify the number of clusters; this number is usually not known in advance and is difficult to estimate. The computational process is very efficient, and the effectiveness of the proposed method is demonstrated in a few real-life examples.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931
Iterative Methods for Sparse Linear Systems
Saad, Y. (2003) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718003 · Cited by 13,790
Self-citationFinding groups in data: an introduction to cluster analysis
(1991) · Choice Reviews Online · doi:10.5860/choice.28-4558 · Cited by 10,474
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Social Network Analysis: A Handbook.
Pappi, F. U., & Scott, J. (1993) · Contemporary Sociology · doi:10.2307/2075047 · Cited by 5,969
Uncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373
Finding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
Finding Groups in Data: An Introduction to Cluster Analysis.
Sarle, W. S., Kaufman, L., & Rousseeuw, P. J. (1991) · Journal of the American Statistical Association · doi:10.2307/2290430 · Cited by 3,539
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,613
An Algorithmic Framework for Performing Collaborative Filtering
Herlocker, J. L., Konstan, J. A., Borchers, A., & Riedl, J. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130372 · Cited by 2,512
NewsWeeder: Learning to Filter Netnews
Lang, K. (1995) · Machine Learning Proceedings 1995 · doi:10.1016/b978-1-55860-377-6.50048-7 · Cited by 2,051
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
An algorithmic framework for performing collaborative filtering
Herlocker, J. L., Konstan, J. A., Borchers, A., & Riedl, J. (1999) · Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/312624.312682 · Cited by 2,011
Co-clustering documents and words using bipartite spectral graph partitioning
Dhillon, I. S. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502550 · Cited by 1,697
Multilevelk-way Partitioning Scheme for Irregular Graphs
Karypis, G., & Kumar, V. (1998) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1997.1404 · Cited by 1,675
Trust-aware recommender systems
Massa, P., & Avesani, P. (2007) · Proceedings of the 2007 ACM conference on Recommender systems · doi:10.1145/1297231.1297235 · Cited by 1,190
Estimation and Prediction for Stochastic Blockstructures
Nowicki, K., & Snijders, T. A. B. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753208735 · Cited by 1,148
Fast Algorithms for Finding Nearest Common Ancestors
Harel, D., & Tarjan, R. E. (1984) · SIAM Journal on Computing · doi:10.1137/0213024 · Cited by 1,073
Information-theoretic co-clustering
Dhillon, I. S., Mallela, S., & Modha, D. S. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956764 · Cited by 1,006
Trawling the Web for emerging cyber-communities
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00040-7 · Cited by 1,000
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Bender, M. A., & Farach-Colton, M. (2000) · Lecture notes in computer science · doi:10.1007/10719839_9 · Cited by 815
Efficient identification of Web communities
Flake, G. W., Lawrence, S., & Giles, C. L. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347121 · Cited by 804
Mixed membership stochastic blockmodels
Airoldi, E. M., Blei, D. M., Fienberg, S. E., & Xing, E. P. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.4485 · Cited by 781
Inferring Web communities from link topology
Gibson, D., Kleinberg, J., & Raghavan, P. (1998) · Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems links, objects, time and space---structure in hypermedia systems - HYPERTEXT '98 · doi:10.1145/276627.276652 · Cited by 768
Clustering on the Unit Hypersphere using von Mises-Fisher Distributions
Banerjee, A., Dhillon, I. S., Ghosh, J., & Sra, S. (2005) · MPG.PuRe (Max Planck Society) · doi:10.5555/1046920.1088718 · Cited by 766
Graph Clustering Via a Discrete Uncoupling Process
Van Dongen, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/040608635 · Cited by 750
Topological structure analysis of the protein-protein interaction network in budding yeast
Bu, D. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg340 · Cited by 747
Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering
Zhao, Y., & Karypis, G. (2004) · Machine Learning · doi:10.1023/b:mach.0000027785.44527.d6 · Cited by 611
Clique Percolation in Random Networks
Derényi, I., Palla, G., & Vicsek, T. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.160202 · Cited by 558
A Spectral Clustering Approach To Finding Communities in Graphs
White, S., & Smyth, P. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.25 · Cited by 404
Finding community structure in mega-scale social networks: [extended abstract]
Wakita, K., & Tsurumi, T. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242805 · Cited by 396
Information-theoretic co-clustering
Dhillon, I. S., Mallela, S., & Modha, D. S. (2003) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956755.956764 · Cited by 361
Massive Quasi-Clique Detection
Abello, J., Resende, M. G. C., & Sudarsky, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45995-2_51 · Cited by 331
A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation
Banerjee, A., Dhillon, I. S., Ghosh, J., et al. (2004) · Cited by 303
Studying Complex Discursive Systems..: Centering Resonance Analysis of Communication
Corman, S. R., Kuhn, T., Mcphee, R. D., & Dooley, K. J. (2002) · Human Communication Research · doi:10.1111/j.1468-2958.2002.tb00802.x · Cited by 274
A Survey of Algorithms for Dense Subgraph Discovery
Lee, V. E., Ruan, N., Jin, R., & Aggarwal, C. (2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0_10 · Cited by 216
Extraction and classification of dense communities in the web
Dourisboure, Y., Geraci, F., & Pellegrini, M. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242635 · Cited by 197
Yokohama, S. (2013) · Discrete mathematics and its applications · doi:10.1201/b16132-52 · Cited by 169
Graph Mining Applications to Social Network Analysis
Tang, L., & Liu, H. (2010) · The Kluwer international series on advances in database systems · doi:10.1007/978-1-4419-6045-0_16 · Cited by 144
Natural communities in large linked networks
Hopcroft, J. E., Khan, O., Kulis, B., & Selman, B. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956816 · Cited by 135
Cited by
CatchSync: catching synchronized behavior in large directed graphs
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623632 · Cited by 151
Catching Synchronized Behaviors in Large Networks: A Graph Mining Approach
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2016) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2746403 · Cited by 88
Inferring Strange Behavior from Connectivity Pattern in Social Networks
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-06608-0_11 · Cited by 82
Inferring lockstep behavior from connectivity pattern in large graphs
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-015-0883-y · Cited by 43
Metadata
- Authors
- Chen, J., & Saad, Y.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2012-07
- Volume
- 24
- Issue
- 7
- Pages
- 1216-1230
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2047923585
- Cited by
- 268
- References
- 47
- FWCI
- 8.21
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.