Yixiang Fang
Abstract
Given a graph G and a vertex q ∈ G, the community search query returns a subgraph of G that contains vertices related to q. Communities, which are prevalent in attributed graphs such as social networks and knowledge bases, can be used in emerging applications such as product advertisement and setting up of social events. In this paper, we investigate the attributed community query (or ACQ), which returns an attributed community (AC) for an attributed graph. The AC is a subgraph of G, which satisfies both structure cohesiveness (i.e., its vertices are tightly connected) and keyword cohesiveness (i.e., its vertices share common keywords). The AC enables a better understanding of how and why a community is formed (e.g., members of an AC have a common interest in music, because they all have the same keyword "music"). An AC can be "personalized"; for example, an ACQ user may specify that an AC returned should be related to some specific keywords like "research" and "sports".
To enable efficient AC search, we develop the CL-tree index structure and three algorithms based on it. We evaluate our solutions on four large graphs, namely Flickr, DBLP, Tencent, and DBpedia. Our results show that ACs are more effective and efficient than existing community retrieval approaches. Moreover, an AC contains more precise and personalized information than that of existing community search and detection methods.
- https://en.wikipedia.org/wiki/Disjoint-set_data_structure.Google Scholar
- V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. arXiv, 2003.Google Scholar
- G. Bhalotia et al. Keyword searching and browsing in databases using banks. In ICDE, 2002.Google ScholarDigital Library
- W. Cui, Y. Xiao, H. Wang, Y. Lu, and W. Wang. Online search of overlapping communities. In SIGMOD, 2013. Google ScholarDigital Library
- W. Cui, Y. Xiao, H. Wang, and W. Wang. Local search of communities in large graphs. In SIGMOD, 2014. Google ScholarDigital Library
- B. Ding, J. X. Yu, S. Wang, L. Qin, X. Zhang, and X. Lin. Finding top-k min-cost connected trees in databases. In ICDE, 2007.Google ScholarCross Ref
- S. N. Dorogovtsev et al. K-core organization of complex networks. Physical review letters, 2006.Google Scholar
- W. Fan, J. Li, S. Ma, N. Tang, Y. Wu, and Y. Wu. Graph pattern matching: from intractable to polynomial time. PVLDB, 2010. Google ScholarDigital Library
- W. Fan, X. Wang, Y. Wu, and J. Xu. Association rules with graph patterns. PVLDB, 8(12):1502--1513, 2015. Google ScholarDigital Library
- Y. Fang, H. Zhang, Y. Ye, and X. Li. Detecting hot topics from twitter: A multiview approach. Journal of Information Science, 40(5):578--593, 2014. Google ScholarDigital Library
- S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75--174, 2010.Google ScholarCross Ref
- J. Han, M. Kamber, and J. Pei. Data mining: concepts and techniques. Elsevier, 2011. Google ScholarDigital Library
- J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. In SIGMOD, 2000. Google ScholarDigital Library
- H. He, H. Wang, J. Yang, and P. S. Yu. Blinks: ranked keyword searches on graphs. In SIGMOD, 2007. Google ScholarDigital Library
- X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. Querying k-truss community in large and dynamic graphs. In SIGMOD, 2014. Google ScholarDigital Library
- V. Kacholia et al. Bidirectional expansion for keyword search on graph databases. In VLDB, 2005. Google ScholarDigital Library
- M. Kargar and A. An. Keyword search in graphs: Finding r-cliques. PVLDB, 4(10):681--692, 2011. Google ScholarDigital Library
- R.-H. Li, L. Qin, J. X. Yu, and R. Mao. Influential community search in large networks. In PVLDB, 2015. Google ScholarDigital Library
- R.-H. Li, J. X. Yu, and R. Mao. Efficient core maintenance in large dynamic graphs. TKDE, 2014.Google ScholarCross Ref
- Y. Liu, A. Niculescu-Mizil, and W. Gryc. Topic-link lda: joint models of topic and author community. In ICML, 2009. Google ScholarDigital Library
- R. M. Nallapati, A. Ahmed, E. P. Xing, and W. W. Cohen. Joint latent topic models for text and citations. In KDD, 2008. Google ScholarDigital Library
- M. Newman et al. Finding and evaluating community structure in networks. Physical review E, 2004.Google Scholar
- Y. Ruan, D. Fuhry, and S. Parthasarathy. Efficient community detection in large networks using content and links. In WWW, 2013. Google ScholarDigital Library
- M. Sachan et al. Using content and interactions for discovering communities in social networks. In WWW, 2012. Google ScholarDigital Library
- S. B. Seidman. Network structure and minimum degree. Social networks, 5(3):269--287, 1983.Google ScholarCross Ref
- M. Sozio and A. Gionis. The community-search problem and how to plan a successful cocktail party. In KDD, 2010. Google ScholarDigital Library
- B. Thomee et al. The new data and new challenges in multimedia research. arXiv:1503.01817, 2015.Google Scholar
- H. Tong, C. Faloutsos, B. Gallagher, and T. Eliassi-Rad. Fast best-effort pattern matching in large attributed graphs. In KDD, 2007. Google ScholarDigital Library
- Z. Xu, Y. Ke, Y. Wang, H. Cheng, and J. Cheng. A model-based approach to attributed graph clustering. In SIGMOD, 2012. Google ScholarDigital Library
- Y. Fang et al. Effective community search for large attributed graphs (technical report). http://www.cs.hku.hk/research/techreps/document/TR-2016-01.pdf.Google Scholar
- J. Yang, J. McAuley, and J. Leskovec. Community detection in networks with node attributes. In ICDM, 2013.Google ScholarCross Ref
- T. Yang, R. Jin, Y. Chi, and S. Zhu. Combining link and content for community detection: a discriminative approach. In KDD, 2009. Google ScholarDigital Library
- J. X. Yu, L. Qin, and L. Chang. Keyword search in databases. Synthesis Lectures on Data Management, 2009. Google ScholarDigital Library
- Y. Zhou, H. Cheng, and J. X. Yu. Graph clustering based on structural/attribute similarities. VLDB, 2009. Google ScholarDigital Library
Index Terms
- Effective community search for large attributed graphs
Recommendations
Effective and efficient attributed community search
Given a graph G and a vertex $$q \in G$$qźG, the community search query returns a subgraph of G that contains vertices related to q. Communities, which are prevalent in attributed graphs such as social networks and knowledge bases, can be used in ...
Keyword aware influential community search in large attributed graphs
AbstractInfluential community search (ICS) on a graph finds a closely connected group of vertices having a dominance over other groups of vertices. The ICS has many applications in recommendations, event organization, and so on. In this paper, ...
Highlights- The query considers user preference (as keywords) for influential community search.
When Structure Meets Keywords: Cohesive Attributed Community Search
CIKM '20: Proceedings of the 29th ACM International Conference on Information & Knowledge ManagementAs an online, query-dependent variant of the well-known community detection problem, community search has been studied for years to find communities containing the query vertices. Along with the generation of graphs with rich attribute information, ...
Comments