PhD Dissertation Proposal by NIU Yudong | Node-centric community search beyond network topology

Community Search, which aims at finding a densely connected subgraph containing a query node, has attracted a lot of attention due to its various real-world applications. Most traditional methods simply consider the distribution of the edges in the network, i.e., the network topology, while searching for the community. However, for many real-world applications, users can have additional requirements for the result community beyond the topological density. For example, for online social marketing, the advertiser wants a community that is not only densely connected but also interested in their product, i.e., the users in the community should be related to a certain topic.  

To this end, in this proposal, we will first discuss several additional requirements that are often stemmed from real-world applications, and then propose algorithms that can return communities satisfying these requirements. First, the community should be related to a certain topic. Second, the query node should be important enough in the result community. To search for communities that can satisfy these two requirements, we first propose a novel index-free community search method LAM over labeled graphs such that the result community is closely related to a query label. Then, to ensure the importance of the query node in the result community, we proposed a two-stage algorithm HUS that can return a community in which the query node is top-k influential.

Niu Yudong is a Ph.D. candidate in the School of Computing and Information Systems, Singapore Management University, supervised by Assistant Professor Li Yuchen. He received his Bachelor's Degree in Computer Science from Wuhan University, China. His research mainly focuses on community search over large networks.