Dissertation
DYNAMIC NETWORK COMMUNITY DETECTION: METRICS, METHODS, AND APPLICATIONS
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2022
DOI:
https://doi.org/10.7273/000004601
Handle:
https://hdl.handle.net/2376/125156
Abstract
Dynamic networks are pervasive in many applications, such as social networks and biological networks. These networks often are characterized by natural divisions that may exist in theinput networks that partition the vertices into coherent modules (or communities) with a higher fraction of links within the communities than between the communities. This dissertation presents detecting communities in time-evolving dynamic networks, a significant operation used in many real-world network science applications. While there have been several proposed strategies for dynamic community detection, such approaches do not necessarily take advantage of the locality of changes. This work presents a new technique called Delta-Screening (or simply, Δ-screening) for updating communities in a dynamic graph. The technique assumes that the graph is given as a series of time steps and outputs a set of communities for each time step. At the start of each time step, the Δ-screening technique examines all changes (edge additions/deletions). It computes a subset of vertices likely to be impacted by the change (using the modularity objective). Subsequently, only the identified subsets are processed for community state updates. Despite the ability of the Δ-screening scheme to prune vertices aggressively, experiments demonstrate that this scheme generates significant savings in runtime performance (up to 38× speedup over static baseline and 5× over dynamic baseline implementations), without compromising quality. We test on both real-world and synthetic network inputs containing both edge additions and deletions. The Δ-screening technique is generic to be incorporated into any existing modularity-optimizing clustering algorithms. We tested using two state-of-the-art clustering implementations, namely, Louvain and SLM. In addition, we also show how to use the Δ-screening approach to delineate appropriate intervals of temporal resolutions at which to analyze a given input network. We introduce a schema using the Δ-screening approach to track the lifespan of temporal communities, which has the flexibility to account for varying community compositions, merging, and splitting behaviors within dynamically evolving networks, and applied our method to chemical networks. When applied to a complex chemical system whose varying chemical environments cause multiple timescale behavior, Δ-screening resolves the hierarchical timescales of temporal communities.
Metrics
5 File views/ downloads
62 Record Views
Details
- Title
- DYNAMIC NETWORK COMMUNITY DETECTION: METRICS, METHODS, AND APPLICATIONS
- Creators
- Neda Zarayeneh
- Contributors
- Ananth Kalyanaraman (Advisor)Janardhan Rao Doppa (Committee Member)Haipeng Cai (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 112
- Identifiers
- 99900901029601842
- Language
- English
- Resource Type
- Dissertation