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 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.
A vertex v having core value k means v has at least k neighbors, each with at least k neighbors, and so on.
Background Research
Investigate Graph Properties
Design approximation algorithm for k-core decomposition
Analyze Complexity and Approximation ratio
Implement the algorithm in Python
Design secure protocol for distributed computation of core value
Analyze Space Complexity
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