### 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.

### 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.

### Neighbor

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

### Degree

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

### Researcher

Wong, Fu Wing

Year 4 Computer Science Student,
the University of Hong Kong

### Supervisor

Chan, T.H., Hubert

Associate Professor,
the University of Hong Kong