Cluster analysis on dynamic graphs
Graph clustering aims to group nodes into a cluster by their features or by some similarity measure, with nodes in the same cluster having higher similarity than those outside of their cluster. Earlier work on graph clustering studied clustering on static graphs, which do not evolve over time. This...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Final Year Project |
Language: | English |
Published: |
Nanyang Technological University
2021
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/153299 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
Summary: | Graph clustering aims to group nodes into a cluster by their features or by some similarity measure, with nodes in the same cluster having higher similarity than those outside of their cluster. Earlier work on graph clustering studied clustering on static graphs, which do not evolve over time. This is in stark contrast to real world graphs, which are dynamic in nature and evolve with the addition and deletion of edges and nodes. Current approaches to dynamic graphs model it as a stream of interactions between nodes, such that any graph event is an interaction in the stream. However, another model of framing dynamic graphs are graph snapshots, which represent the state of the graph at different timestamps. For systems lacking fine-grained time measures, such graph snapshots are the only way to capture the temporal nature of the graph. This paper addresses the topic of graph clustering, first in the static domain and secondly in the dynamic
domain, where the graph can evolve over time. We examine prior work in graph clustering, from the unsupervised methods initially where we optimize the clusters based on some quality measure to the application of graph neural networks on graph clustering. Next, we apply the concept of temporal attention along with transitional recurrent neural networks to the
topic of dynamic graph clustering on graph snapshots. We then formulate a concept of temporal attention over graph snapshots and apply this to create our model. The results obtained from the model beat out transitional recurrent neural networks using graph convolution and empirical data shows that there is a gain in accuracy from this encoding of temporal attention. |
---|