From Community Detection to Community Search

Laks V.S. Lakshmanan
Computer Science, University of British Columbia


Communities naturally exist in many real-world networks such as social, biological, collaboration, and communication networks and serve as an invaluable tool for organizing and understanding their structure. This has led to substantial research into their detection. Recently, community search has gained increasing attention. In contrast with community detection, the objective of this problem is to find the community containing given query nodes. I will discuss alternative community models and challenges arising in community definition and search. I will then focus on community search over deterministic graphs, using the recently proposed "k-truss" model, motivated by the many desirable properties of trusses compared to alternative community models. I will show that finding the exact query k-truss community is intractable in general and present scalable approximation and heuristic algorithms. In several applications, the network links tend to be inherently uncertain. How should we define k-truss communities over probabilistic graphs? (How) Can we find them efficiently? These are some of the questions I will address next. I will offer empirical evidence of the advantages and promise of the truss based community model over competing approaches, based on experiments over real datasets. I will conclude the talk with interesting questions for future research.