Overlapped Community Detection in Multiplex Networks

Potential supervisors: 
Description: 

Community detection in graphs is a classical problem. In community detection, groups of individual nodes with high level of interconnectivity are detected. Despite the established computational hardness of community detection, there exists a wide range of practical and effective techniques for solving it. Many of them are based on graph partitioning (clustering) and clique detection methods.

Community detection becomes more difficult if the communities overlap, i.e. they have shared nodes. Graph partitioning techniques are not successful in this case. To alleviate this problem, it is sometimes possible to divide a graph into multiple graphs based on some attributes of the nodes. An example is a social network, where each node is a user/account and the friendship graph can be divided by attributes that each user selects (interest/activities/etc). Once a graph is divided into many graphs, it forms a multiplex network. The hope is that the overlapping communities do not appear in a common subgraph (called a layer) and hence they can be detected by the traditional graph partitioning techniques. However, since each layer has fewer edges, this can be a difficult task and often requires to jointly detect from every layer.

This thesis is about overlapped community detection by such multiplex networks.

The main objectives are listed below:

  • To study the literature and find community detection techniques that can handle overleaping communities and/or multiplex networks, e.g. [1]
  • To implement and compare these techniques on benchmark datasets. Examples of such datasets [2].
  • To extend and implement the so-called nuclear(trace) norm graph clustering over multiplex networks, e.g. [3], [4].

The students are required to implement a convex optimization algorithm for the last part.

Prerequisites: A course in algorithms, good programming skills and general familiarity with convex optimization.

Suitable for 1-2 students (preferably 2).

[1] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&

[2] http://networkrepository.com/socfb-Caltech36.php

[3] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6855219

[4] https://arxiv.org/pdf/0901.3348.pdf

 

Contact: Ashkan dot Panahi at chalmers dot se

Date range: 
September, 2020 to September, 2025