Distributed / Dynamic k-core decomposition

Networks such as social relationship, bio information and earthquake frequencies can be modeled as a graph. K-core decomposition is a tool to visualize, understand and analyze a graph for studying graph properties. A linear time algorithm is used to obtain exact core value for centralized scenario, where the whole graph is known. There also exists an linear algorithm for decentralized scenario, where every node and vertex only knows information of itself and its neighbors.

Graph mining may not require exact core values. Approximating core values will be faster while keeping usability of the calculated core values.

There might be dishonest vertices in real world application, calculating core values in decentralized scenario require extra attention. Using fake information retrieved will results in calculating wrong core value. A secure protocol is needed to authenticate information retrieved, and perform calculation with only authenticated information.

This project will focus on :
1.    Designing an approximation algorithm for k-core decomposition in distributed scenario
2.   Designing a secure protocol for distributed core value calculation using only authenticated information.

k-core decomposition

k-core decomposition is a graph problem of calculating core values for every vertices in a graph.


A graph consists of vertices(points) and edges(lines).
The collection of vertices and edges are denoted as V and E = (u, v ) respectively.


Two vertices u and v are neighbors if they are connected, i.e. there is a line connecting u and v .


Degree of a vertex v is the number of v 's neighbors.

Core Value

A vertex v having core value k means v has at least k neighbors, each with at least k neighbors, and so on.

Project Progress

  •   30 September, 2018

    Background Research

  •   20 November, 2018

    Investigate Graph Properties

  •   10 January, 2019

    Design approximation algorithm for k-core decomposition
    Analyze Complexity and Approximation ratio
    Implement the algorithm in Python

  •   28 February, 2019

    Design secure protocol for distributed computation of core value
    Analyze Space Complexity

  •   31 March, 2019

    Implement the protocol in Python
    Simulation on randomly generated graphs


Wong, Fu Wing

Year 4 Computer Science Student,
the University of Hong Kong


Chan, T.H., Hubert

Associate Professor,
the University of Hong Kong