Fan Zhang
Abstract
In this paper, we investigate the problem of (k,r)-core which intends to find cohesive subgraphs on social networks considering both user engagement and similarity perspectives. In particular, we adopt the popular concept of k-core to guarantee the engagement of the users (vertices) in a group (subgraph) where each vertex in a (k,r)-core connects to at least k other vertices. Meanwhile, we consider the pairwise similarity among users based on their attributes. Efficient algorithms are proposed to enumerate all maximal (k,r)-cores and find the maximum (k,r)-core, where both problems are shown to be NP-hard. Effective pruning techniques substantially reduce the search space of two algorithms. A novel (k,k')-core based (k,r)-core size upper bound enhances performance of the maximum (k,r)-core computation. We also devise effective search orders for two mining algorithms where search priorities for vertices are different. Comprehensive experiments on real-life data demonstrate that the maximal/maximum (k,r)-cores enable us to find interesting cohesive subgraphs, and performance of two mining algorithms is effectively improved by proposed techniques.
- How does facebook suggest groups for me to join? https://www.facebook.com/help/382485908586472?helpref=uf_permalink. Accessed: 14 Mar. 2017.Google Scholar
- V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. CoRR, cs.DS/0310049, 2003.Google Scholar
- K. Bhawalkar, J. M. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma. Preventing unraveling in social networks: The anchored k-core problem. SIAM J. Discrete Math., 29(3):1452--1475, 2015.Google ScholarDigital Library
- C. Bird, A. Gourley, P. T. Devanbu, M. Gertz, and A. Swaminathan. Mining email social networks. In MSR, pages 137--143, 2006. Google ScholarDigital Library
- C. Bron and J. Kerbosch. Finding all cliques of an undirected graph (algorithm 457). Commun. ACM, 16(9):575--576, 1973. Google ScholarDigital Library
- L. Chang, J. X. Yu, and L. Qin. Fast maximal cliques enumeration in sparse graphs. Algorithmica, 66(1):173--186, 2013.Google ScholarCross Ref
- K. Chen and C. Lei. Network game design: hints and implications of player interaction. In NETGAMES, page 17, 2006. Google ScholarDigital Library
- J. Cheng, L. Zhu, Y. Ke, and S. Chu. Fast algorithms for maximal clique enumeration with limited memory. In KDD, pages 1240--1248, 2012. Google ScholarDigital Library
- D. Eppstein and D. Strash. Listing all maximal cliques in large sparse real-world graphs. In SEA, pages 364--375, 2011. Google ScholarDigital Library
- Y. Fang, R. Cheng, X. Li, S. Luo, and J. Hu. Effective community search over large spatial graphs. PVLDB, 10(6):709--720, 2017. Google ScholarDigital Library
- Y. Fang, R. Cheng, S. Luo, and J. Hu. Effective community search for large attributed graphs. PVLDB, 9(12):1233--1244, 2016. Google ScholarDigital Library
- Y. Fang, H. Zhang, Y. Ye, and X. Li. Detecting hot topics from twitter: A multiview approach. J. Information Science, 40(5):578--593, 2014. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. JACM, 23(1):43--49, 1976. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google ScholarDigital Library
- M. K. Goldberg, S. Kelley, M. Magdon-Ismail, K. Mertsalov, and A. Wallace. Finding overlapping communities in social networks. In SocialCom/PASSAT, pages 104--113, 2010. Google ScholarDigital Library
- D. Hristova, M. Musolesi, and C. Mascolo. Keep your friends close and your facebook friends closer: A multiplex network approach to the analysis of offline and online social ties. In ICWSM, 2014.Google Scholar
- X. Huang, W. Lu, and L. V. S. Lakshmanan. Truss decomposition of probabilistic graphs: Semantics and algorithms. In SIGMOD, pages 77--90, 2016. Google ScholarDigital Library
- J. J. P. III, S. Moreno, T. L. Fond, J. Neville, and B. Gallagher. Attributed graph models: modeling network structure with correlated attributes. In WWW, pages 831--842, 2014. Google ScholarDigital Library
- M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature physics, 6(11):888--893, 2010.Google ScholarCross Ref
- M. Kivelä and e. Arenas. Multilayer networks. Journal of Complex Networks, 2(3):203--271, 2014.Google ScholarCross Ref
- P. Lee, L. V. S. Lakshmanan, and E. E. Milios. CAST: A context-aware story-teller for streaming social content. In CIKM, pages 789--798, 2014. Google ScholarDigital Library
- F. D. Malliaros and M. Vazirgiannis. To stay or not to stay: modeling engagement dynamics in social graphs. In CIKM, pages 469--478, 2013. Google ScholarDigital Library
- A. Nanopoulos, H. Gabriel, and M. Spiliopoulou. Spectral clustering in social-tagging systems. In WISE, pages 87--100, 2009. Google ScholarDigital Library
- S. B. Seidman. Network structure and minimum degree. Social networks, 5(3):269--287, 1983.Google ScholarCross Ref
- P. Singla and M. Richardson. Yes, there is a correlation - from social networks to personal behavior on the web. In WWW, pages 655--664, 2008. Google ScholarDigital Library
- J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. PNAS, 109(16):5962--5966, 2012.Google ScholarCross Ref
- J. Wang, J. Cheng, and A. W. Fu. Redundancy-aware maximal cliques. In KDD, pages 122--130, 2013. Google ScholarDigital Library
- D. Wen, L. Qin, Y. Zhang, X. Lin, and J. X. Yu. I/O efficient core graph decomposition at web scale. In ICDE, pages 133--144, 2016.Google ScholarCross Ref
- S. Wu, A. D. Sarma, A. Fabrikant, S. Lattanzi, and A. Tomkins. Arrival and departure dynamics in social networks. In WSDM, pages 233--242, 2013. Google ScholarDigital Library
- Y. Wu, R. Jin, X. Zhu, and X. Zhang. Finding dense and connected subgraphs in dual networks. In ICDE, pages 915--926, 2015.Google ScholarCross Ref
- Z. Xu, Y. Ke, Y. Wang, H. Cheng, and J. Cheng. A model-based approach to attributed graph clustering. In SIGMOD, pages 505--516, 2012. Google ScholarDigital Library
- J. Yang, J. J. McAuley, and J. Leskovec. Community detection in networks with node attributes. In ICDM, pages 1151--1156, 2013.Google ScholarCross Ref
- F. Zhang, W. Zhang, Y. Zhang, L. Qin, and X. Lin. OLAK: an efficient algorithm to prevent unraveling in social networks. PVLDB, 10(6):649--660, 2017. Google ScholarDigital Library
- F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin. Finding critical users for social network engagement: The collapsed k-core problem. In AAAI, pages 245--251, 2017.Google ScholarDigital Library
- Q. Zhu, H. Hu, J. Xu, and W. Lee. Geo-social group queries with minimum acquaintance constraint. CoRR, abs/1406.7367, 2014.Google Scholar
Index Terms
- When engagement meets similarity: efficient (k,r)-core computation on social networks
Recommendations
Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms
In the Split Vertex Deletion problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the ...
Linear rankwidth meets stability
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete AlgorithmsClasses with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the properties of these graph classes considered from the point of view of ...
Self-Similarity of Graphs
An old problem raised independently by Jacobson and Schönheim seeks to determine the maximum $s$ for which every graph with $m$ edges contains a pair of edge-disjoint isomorphic subgraphs with $s$ edges. In this paper we determine this maximum up to a ...
Comments