Abstract/Details

Gridlock in Networks: The Leximin Method for Hierarchical Community Detection

McCarthy, Arya D.   Southern Methodist University ProQuest Dissertations Publishing,  2017. 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 (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences; Clustering; Community detection; Graph theory; Linear programming; Maximum concurrent flow problem
Title
Gridlock in Networks: The Leximin Method for Hierarchical Community Detection
Author
McCarthy, Arya D.
Number of pages
93
Degree date
2017
School code
0210
Source
MAI 56/04M(E), Masters Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
978-1-369-79880-7
Advisor
Matula, David W.
Committee member
Engels, Daniel W.; Larson, Eric C.; Olinick, Eli V.
University/institution
Southern Methodist University
Department
Computer Science and Engineering
University location
United States -- Texas
Degree
M.S.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
10284688
ProQuest document ID
1907180434
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/1907180434