WalkSCAN: Improving PageRank for local community detection

Speaker : Alexandre Holloucou
Date: 16/11/2016
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


Community detection is a fundamental problem in the field of graph mining. The objective is to find densely connected clusters of nodes, so-called communities, possibly overlapping. While most existing algorithms work on the entire graph, it is often irrelevant in practice to cluster all nodes. A more practically interesting problem is to detect the community to which a given set of nodes, the so-called “seed nodes”, belong. Moreover, the exploration of the whole network is generally computationally expensive, if not impossible, and algorithms that only take into account the local structure of the graph around seed nodes provide a big advantage. For these reasons, there is a growing interest in the problem of “local” community detection, also known as “seed set expansion”. We solve this problem through a low-dimensional embedding of the graph based on random walks starting from the seed nodes.