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.
|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|
|Keywords:||Clustering, Community detection, Graph theory, Linear programming, Maximum concurrent flow problem|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be