article

Large scale cohesive subgraphs discovery for social network visual analysis

Authors:

Anthony K. H. TungAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 6, Issue 2

Pages 85 - 96

https://doi.org/10.14778/2535568.2448942

Published: 01 December 2012 Publication History

Abstract

Graphs are widely used in large scale social network analysis nowadays. Not only analysts need to focus on cohesive subgraphs to study patterns among social actors, but also normal users are interested in discovering what happening in their neighborhood. However, effectively storing large scale social network and efficiently identifying cohesive subgraphs is challenging. In this work we introduce a novel subgraph concept to capture the cohesion in social interactions, and propose an I/O efficient approach to discover cohesive subgraphs.

Besides, we propose an analytic system which allows users to perform intuitive, visual browsing on large scale social networks. Our system stores the network as a social graph in the graph database, retrieves a local cohesive subgraph based on the input keywords, and then hierarchically visualizes the subgraph out on orbital layout, in which more important social actors are located in the center. By summarizing textual interactions between social actors as tag cloud, we provide a way to quickly locate active social communities and their interactions in a unified view.

References

[1]

R. D. Alba. A graph-theoretic definition of a sociometric clique. Journal of Mathematical Sociology, pages 113-126, 1973.

[2]

J. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. K-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, page 371, 2008.

[3]

E. Bakshy, I. Rosenn, C. Marlow, and L. Adamic. The role of social networks in information diffusion. In WWW, 2012.

[4]

U. Brandes and C. Pich. More flexible radial layout. J. Graph Algorithms Appl., pages 107-118, 2011.

[5]

A. Budanitsky and G. Hirst. Semantic distance in wordnet: An experimental, application-oriented evaluation of five measures. In Workshop on WordNet and Other Lexical Resources, 2001.

[6]

J. Cheng, Y. Ke, S. Chu, and M. Ozsu. Efficient core decomposition in massive networks. In ICDE, pages 51-62, 2011.

[7]

S. Chu and J. Cheng. Triangle listing in massive networks and its applications. In SIGKDD, pages 672-680, 2011.

[8]

C. Correa, T. Crnovrsanin, and K. Ma. Visual reasoning about social networks using centrality sensitivities. TVCG, pages 1-15, 2010.

[9]

U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is almost np-complete. In FOCS, pages 2-12, 1991.

[10]

http://en.wikipedia.org/wiki/FlockDB.

[11]

T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Software: Practice and experience, pages 1129-1164, 1991.

[12]

E. Gilbert and K. Karahalios. Predicting tie strength with social media. In CHI, pages 211-220, 2009.

[13]

P. A. Grabowicz, J. J. Ramasco, E. Moro, J. M. Pujol, and V. M. Eguluz. Social features of online networks: the strength of weak ties in online social media. CoRR, 2011.

[14]

M. Granovetter. The strength of weak ties. American journal of sociology, pages 1360-1380, 1973.

[15]

R. Luce. Connectivity and generalized cliques in sociometric group structure. Psychometrika, pages 169-190, 1950.

[16]

R. Luce and A. Perry. A method of matrix analysis of group structure. Psychometrika, pages 95-116, 1949.

[17]

M. Rodriguez and P. Neubauer. The graph traversal pattern. In Graph Data Management, pages 29-46, 2011.

[18]

S. Seidman. Network structure and minimum degree. Social networks, pages 269-287, 1983.

[19]

S. Seidman and B. Foster. A graph-theoretic generalization of the clique concept. Journal of Mathematical sociology, pages 139-154, 1978.

[20]

I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In WWW, 2012.

[21]

J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su. Arnetminer: extraction and mining of academic social networks. In SIGKDD, pages 990-998, 2008.

[22]

J. Wang and J. Cheng. Truss decomposition in massive networks. Proceedings of the VLDB Endowment, 5(9):812-823, 2012.

[23]

N. Wang, S. Parthasarathy, K. Tan, and A. Tung. Csv: visualizing and mining cohesive subgraphs. In SIGMOD, pages 445-458, 2008.

[24]

N. Wang, J. Zhang, K. Tan, and A. Tung. On triangulation-based dense neighborhood graph discovery. In VLDB, pages 58-68, 2010.

[25]

D. White and F. Harary. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology, pages 305-359, 2001.

[26]

Y. Zhang and S. Parthasarathy. Extracting analyzing and visualizing triangle k-core motifs within networks. In ICDE, 2011.

Cited By

Zhang WYang ZWen DLi WZhang WLin X(2025)Accelerating Core Decomposition in Billion-Scale HypergraphsProceedings of the ACM on Management of Data10.1145/37096563:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709656
Zhang YLi RZhang QQin HWang G(2024)Efficient Algorithms for Density Decomposition on Large Static and Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368197417:11(2933-2945)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.14778/3681954.3681974
Zhang YLi RZhang QQin HQin LWang G(2024)Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368195817:11(2722-2734)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.14778/3681954.3681958
Show More Cited By

Index Terms

Large scale cohesive subgraphs discovery for social network visual analysis

Recommendations

Spanning Eulerian Subgraphs of Large Size

A graph $$G=(V(G), E(G))$$G=(V(G),E(G)) is supereulerian if it has a spanning Eulerian subgraph. Let $$\ell (G)$$ℓ(G) be the maximum number of edges of spanning Eulerian subgraphs of a graph G. Motivated by a conjecture due to Catlin on supereulerian ...
Disjoint subgraphs of large maximum degree

Erdös [in: Chartrand (Ed.), The Theory and Applications of Graphs, Wiley, New York, 1981, p. 331] conjectured that the vertices of any graph with fewer than (2n+1 2) - (n 2) edges can be split into two parts, both parts inducing subgraphs of maximum ...
Odd Induced Subgraphs in Planar Graphs with Large Girth
Abstract
A long-standing conjecture asserts that there is a positive constant c such that every n-vertex graph without isolated vertices contains an induced subgraph with all degrees odd on at least cn vertices. Recently, Ferber and Krivelevich confirmed ... $^{}$ $^{}$ $^{}$ $_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 6, Issue 2

December 2012

120 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 December 2012

Published in PVLDB Volume 6, Issue 2

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

88
Total Citations
View Citations
340
Total Downloads

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

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WYang ZWen DLi WZhang WLin X(2025)Accelerating Core Decomposition in Billion-Scale HypergraphsProceedings of the ACM on Management of Data10.1145/37096563:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709656
Zhang YLi RZhang QQin HWang G(2024)Efficient Algorithms for Density Decomposition on Large Static and Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368197417:11(2933-2945)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.14778/3681954.3681974
Zhang YLi RZhang QQin HQin LWang G(2024)Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368195817:11(2722-2734)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.14778/3681954.3681958
Xu XLiu HLv XWang YLi D(2024)An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph DiscoveryProceedings of the ACM on Management of Data10.1145/36988002:6(1-26)Online publication date: 20-Dec-2024
https://dl.acm.org/doi/10.1145/3698800
Zhou YGuo QFang YMa C(2024)A Counting-based Approach for Efficient k-Clique Densest Subgraph DiscoveryProceedings of the ACM on Management of Data10.1145/36549222:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654922
Shi JDhulipala LShun J(2024)Parallel Algorithms for Hierarchical Nucleus DecompositionProceedings of the ACM on Management of Data10.1145/36392872:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639287
Chu DZhang FZhang WLin XZhang YXia YZhang C(2024)Discovering and Maintaining the Best $k$k in Core DecompositionIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338998936:11(5954-5971)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3389989
Kerdcharoen YSridhar USangpetch OLow T(2024)Linear Algebra Approach for Directed Triad Counting and EnumerationProceedings of the SC '24 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis10.1109/SCW63240.2024.00100(718-726)Online publication date: 17-Nov-2024
https://dl.acm.org/doi/10.1109/SCW63240.2024.00100
Tatti N(2024)Explainable decomposition of nested dense subgraphsData Mining and Knowledge Discovery10.1007/s10618-024-01053-838:6(3621-3642)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1007/s10618-024-01053-8
Zheng YZhang ZLuo QXie ZYu D(2023)A Truss-Based Framework for Graph Similarity ComputationJournal of Database Management10.4018/JDM.32208734:1(1-18)Online publication date: 21-Apr-2023
https://dl.acm.org/doi/10.4018/JDM.322087
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents