Understanding the Structure of Complex Networks with Community Detection

Date

2017-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Modularity is the most widely used metric in the field of community detection for complex networks. This dissertation is about the successful integration of modularity based community detection method into developing powerful computational and visual analytic tools to enhance comprehension of the structures across various types of networks.

We develop a novel computational workflow to identify robust functional modules in Escherichia coli. An ensemble study using modularity optimization is performed to study weighted unipartite networks inferred from gene expression data. We introduce simulated annealing and a `three body' correlation technique to visualize and identify novel structures related to every gene. A few robust functional gene groups are found within these structures.

We also study bipartite networks with modularity optimization. First a typical study on a small network is briefly discussed. Then we introduce a computational framework which integrates modularity and other metrics to automatically identify important comprehensible sub-networks from very large and messy networks. The framework generates significant results in the study of several medical networks.

Community detection based on modularity is also integrated to develop a new 2D layout algorithm for networks. The algorithm takes as input an initial layout from some traditional algorithms and the community detection result of the network. Then a new layout is generated based on certain geometrical calculation and optimization technique. The algorithm is proved to have significantly improved the readability of networks from the opinion of corresponding domain experts.

Finally, we discuss in detail the resolution limit problem of modularity and a recently introduced metric named modularity density which claims to have solved the problem. We point out that modularity density does not completely solve the problem while even cause new ones. We introduce a new metric which further mitigates the problem and generate better results on benchmark networks.

Description

Keywords

Community detection, Modularity

Citation