Back to search

University of British Columbia

Community detection in sparse time-varying networks

Abstract

dc:description

Community detection is an important aspect of network analysis that has far-reaching consequences, in particular for biological research. In the study of systems biology, it is important to detect communities in biological networks to identify areas that have a heavy correlation between one another or are significant for biological functions. If one were to model networks that evolved over time, a differential network would be a vital part or product of that analysis. One such network could have an edge between two vertices if there is a significant change in the correlation of expression levels between the two genes that the vertices are designed to model. For this particular network, there are no community detection algorithms that suffice. An analysis of the current community detection algorithms shows that most heuristic-based methods are too simple or have too high a cost for detecting communities on such sparse networks. A prototypical algorithm is presented that is preferential to high weight edges when determining community membership. This algorithm, Weighted Sparse Community Finder or WSCF, is an incremental algorithm that develops community structure from highly-weighted community seeds, which are 3-vertex substructures in the network with a high local modularity. A preliminary analysis of this detection algorithm shows that it is functional on data sets consisting of up to 600 genes, with more on a more powerful machine. The communities detected are different than the ones provided by the benchmark algorithms because of the high precedence placed on higher-weight edges. This prototypical algorithm has the potential for refinement and expansion to provide the ability to find significant results for applications in the field of Systems Biology.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Slind, Jillian Rae

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 2.5 Canada
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/50043

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Slind, Jillian Rae. Community detection in sparse time-varying networks. master's thesis, University of British Columbia, 2014. http://hdl.handle.net/2429/50043