Mining Persistent and Discriminative Communities in Graph Ensembles
Article No.: 28, Pages 1 - 6
Abstract
Detecting all communities in a single graph is a prevalent task in graph data analytics. However, many scientific applications naturally create data as an ensemble of graphs. For example, graph ensembles can be created from multiple: social networks at distinct points in time, biological networks created from independent experiments, and global climate networks created from unique climate models. In this work, we present a method for enumerating community subsets across an ensemble of graphs, with the ability to detect both persistent and discriminative subcommunities. Moreover, we support queries, consisting of user-specified vertices of interest and arbitrary ensemble slices, to produce output that is more relevant to the user while reducing output size and computation time. While related methods are designed around a single community definition, our method is designed around the idea that choosing an appropriate community definition often depends on the application at hand. Therefore, our goal is to provide a framework that can leverage the abundance of community detection methods available when discovering persistent and discriminative substructures.
References
[1]
Thomas Aynaud, Eric Fleury, Jean-Loup Guillaume, and Qinna Wang. 2013. Communities in evolving networks: definitions, detection, and analysis techniques. In Dynamics On and Of Complex Networks, Volume 2. Springer, 159--200.
[2]
Gonzalo A Bello, Steve Harenberg, Abhishek Agrawal, and Nagiza F Samatova. 2016. Community Detection in Dynamic Attributed Graphs. In Advanced Data Mining and Applications: 12th International Conference. Springer, 329--344.
[3]
Hong Cheng, Xifeng Yan, Jiawei Han, and Philip S. Yu. 2008. Direct Discriminative Pattern Mining for Effective Classification. In Proceedings of the 24th International Conference on Data Engineering, ICDE. 169--178.
[4]
Gösta Grahne and Jianfei Zhu. 2005. Fast Algorithms for Frequent Itemset Mining Using FP-Trees. IEEE Trans. Knowl. Data Eng. 17, 10 (2005), 1347--1362.
[5]
Daxin Jiang and Jian Pei. 2009. Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data (TKDD) 2, 4 (2009), 16.
[6]
Ning Jin and Wei Wang. 2011. LTS: Discriminative subgraph mining by learning from search history. In Proceedings of the 27th International Conference on Data Engineering, ICDE. 207--218.
[7]
Ning Jin and Wei Wang. 2014. Mining Discriminative Subgraph Patterns from Structural Data. In Data Mining and Knowledge Discovery for Big Data. Springer, 117--152.
[8]
Ning Jin, Calvin Young, and Wei Wang. 2010. GAIA: graph classification using evolutionary computation. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD. 879--890.
[9]
Siyuan Liu, Shuhui Wang, and Ramayya Krishnan. 2014. Persistent Community Detection in Dynamic Social Networks. In Advances in Knowledge Discovery and Data Mining - 18th Pacific-Asia Conference, PAKDD. 78--89.
[10]
Kathy Macropol and Ambuj Singh. 2010. Scalable discovery of best clusters on large graphs. Proceedings of the VLDB Endowment, PVLDB 3, 1--2 (2010), 693--702.
[11]
Peter J Mucha, Thomas Richardson, Kevin Macon, Mason A Porter, and Jukka-Pekka Onnela. 2010. Community structure in time-dependent, multiscale, and multiplex networks. Science 328, 5980 (2010), 876--878.
[12]
Mark EJ Newman. 2006. Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103, 23 (2006), 8577--8582.
[13]
Kouzou Ohara, Masahiro Hara, Kiyoto Takabayashi, Hiroshi Motoda, and Takashi Washio. 2008. Pruning Strategies Based on the Upper Bound of Information Gain for Discriminative Subgraph Mining. In Knowledge Acquisition: Approaches, Algorithms and Applications, Pacific Rim Knowledge Acquisition Workshop, PKAW. 50--60.
[14]
Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043 (2005), 814--818.
[15]
Matthew C. Schmidt, Andrea M. Rocha, Kanchana Padmanabhan, Zhengzhang Chen, Kathleen Scott, James R. Mihelcic, and Nagiza F. Samatova. 2011. Efficient alpha, beta-motif Finder for Identification of Phenotype-related Functional Modules. BMC Bioinformatics 12 (2011), 440.
[16]
Chayant Tantipathananandh and Tanya Y. Berger-Wolf 2011. Finding Communities in Dynamic Social Networks. In 11th IEEE International Conference on Data Mining, ICDM. 1236--1241.
[17]
Marisa Thoma, Hong Cheng, Arthur Gretton, Jiawei Han, Hans-Peter Kriegel, Alexander J. Smola, Le Song, Philip S. Yu, Xifeng Yan, and Karsten M. Borgwardt. 2009. Near-optimal Supervised Feature Selection among Frequent Subgraphs. In SIAM International Conference on Data Mining, SDM. SIAM, 1076--1087.
[18]
Xifeng Yan, Hong Cheng, Jiawei Han, and Philip S. Yu. 2008. Mining significant graph patterns by leap search. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD. 433--444.
[19]
Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-Based Substructure Pattern Mining. In Proceedings of the 2002 IEEE International Conference on Data Mining ICDM. 721--724.
Index Terms
- Mining Persistent and Discriminative Communities in Graph Ensembles
Recommendations
Out-of-bag discriminative graph mining
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied ComputingIn class-labeled graph databases, each graph is associated with one from a finite set of classes, which induces associations between classes and subgraphs occurring in the database graphs. The subgraphs with strong class associations are called ...
Compression of community graph using graph mining techniques
Representation of any network graphically has vast applications and used for knowledge extraction efficiently. Due to the increase in applications of a graph, the size of the graph becomes larger as well as its complexity becomes more and more. So ...
Building member attachment in online communities: applying theories of group identity and interpersonal bonds
Online communities are increasingly important to organizations and the general public, but there is little theoretically based research on what makes some online communities more successful than others. In this article, we apply theory from the field of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2017
373 pages
ISBN:9781450352826
DOI:10.1145/3085504
- General Chair:
- Alok Choudhary,
- Program Chair:
- Kesheng Wu,
- Publications Chair:
- Bin Dong
Copyright © 2017 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 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].
In-Cooperation
- Northwestern University: Northwestern University
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 June 2017
Check for updates
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
SSDBM '17
SSDBM '17: 29th International Conference on Scientific and Statistical Database Management
June 27 - 29, 2017
IL, Chicago, USA
Acceptance Rates
Overall Acceptance Rate 56 of 146 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 113Total Downloads
- Downloads (Last 12 months)38
- Downloads (Last 6 weeks)6
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in