COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Gridlock in Networks: The Leximin Method for Hierarchical Community Detection
by McCarthy, Arya D., M.S., Southern Methodist University, 2017, 93; 10284688
Abstract (Summary)

Community detection (CD) is an important task in network science. Identifying the community structure and hierarchy of communities reveals latent properties of the network. This task has real-world relevance in social network analysis, taxonomy, bioinformatics, and graph mining in general. Nevertheless, there is no common definition of a community and no common, efficient method of identifying communities. As is common, we formulate CD as optimization of modularity. Modularity quantifies the separation of a network into distinct, highly interconnected groups. Maximizing modularity is NP-hard.

To solve the optimization problem, we present a polynomial-time approximation method. It greedily maximizes modularity with a heuristic for sparsest cuts in a network. This involves maximizing max-min fair throughput between all pairs of network nodes. We evaluate the approximation’s effectiveness for CD on synthetic networks with known community structure. We show competitive results in terms of the standard measure of CD accuracy, normalized mutual information (NMI). Further, our method is less sensitive to network perturbations than existing community detection algorithms. Our method also detects ties in hierarchical structure, which other techniques do not.

In graphs without a strong community structure, our method does not impose arbitrary structure. In these cases, we can show that the max-min fair flow can be split onto edge-disjoint paths of a multigraph corresponding to the original network.

Indexing (document details)
Advisor: Matula, David W.
Commitee: Engels, Daniel W., Larson, Eric C., Olinick, Eli V.
School: Southern Methodist University
Department: Computer Science and Engineering
School Location: United States -- Texas
Source: MAI 56/04M(E), Masters Abstracts International
Subjects: Computer science
Keywords: Clustering, Community detection, Graph theory, Linear programming, Maximum concurrent flow problem
Publication Number: 10284688
ISBN: 978-1-369-79880-7
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy