Structural Correlation Pattern Mining for Large Graphs

• Ariel Silva UFMG
• Wagner Meira Jr. UFMG

Resumo

How are personal interests related to the communities in large social networks? In order to answer this kind of question, we introduce structural correlation pattern mining, which is the identification of interesting associations between vertex attributes and dense subgraphs. We present a model and algorithms that explore search, pruning, sampling and parallelization strategies to solve this problem for large graphs. Results show that structural correlation pattern mining enables the discovery of relevant patterns in real-life datasets.

Referências

Anagnostopoulos, A., Kumar, R., and Mahdian, M. (2008). Influence and correlation in social networks. In SIGKDD, pages 7–15. ACM.

Chakrabarti, D. and Faloutsos, C. (2006). Graph mining: Laws, generators, and algorithms. ACM Comput. Surv., 38(1).

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

Liu, G. and Wong, L. (2008). Effective pruning techniques for mining quasi-cliques. In ECML/PKDD, pages 33–49. Springer-Verlag.

Silva, A. (2011). Structural correlation pattern mining for large graphs. M.Sc Thesis, Computer Science Department, Universidade Federal de Minas Gerais.

Silva, A., Meira, Jr., W., and Zaki, M. J. (2010). Structural correlation pattern mining for large graphs. In MLG, pages 119–126. ACM.

Silva, A., Meira, Jr., W., and Zaki, M. J. (2012). Mining attribute-structure correlated patterns in large attributed graphs. Proc. of the VLDB Endowment, 5(5):466–477.