Complex network analysis using modulus of families of walks

K-REx Repository

Show simple item record

dc.contributor.author Shakeri, Heman
dc.date.accessioned 2017-05-15T14:27:09Z
dc.date.available 2017-05-15T14:27:09Z
dc.date.issued 2017-05-01 en_US
dc.identifier.uri http://hdl.handle.net/2097/35593
dc.description.abstract The modulus of a family of walks quantifies the richness of the family by favoring having many short walks over a few longer ones. In this dissertation, we investigate various families of walks to study new measures for quantifying network properties using modulus. The proposed new measures are compared to other known quantities. Our proposed method is based on walks on a network, and therefore will work in great generality. For instance, the networks we consider can be directed, multi-edged, weighted, and even contain disconnected parts. We study the popular centrality measure known in some circles as information centrality, also known as effective conductance centrality. After reinterpreting this measure in terms of modulus of families of walks, we introduce a modification called shell modulus centrality, that relies on the egocentric structure of the graph. Ego networks are networks formed around egos with a specific order of neighborhoods. We then propose efficient analytical and approximate methods for computing these measures on both directed and undirected networks. Finally, we describe a simple method inspired by shell modulus centrality, called general degree, which improves simple degree centrality and could prove to be a useful tool for practitioners in the applied sciences. General degree is useful for detecting the best set of nodes for immunization. We also study the structure of loops in networks using the notion of modulus of loop families. We introduce a new measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link-usage optimally. We propose weighting networks using these expected link-usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks. Computing loop modulus benefits from efficient algorithms for finding shortest loops, thus we propose a deterministic combinatorial algorithm that finds a shortest cycle in graphs. The proposed algorithm reduces the worst case time complexity of the existing combinatorial algorithms while visiting at most the cycle basis. For most empirical networks with sublinear average degree our algorithm is subcubic. en_US
dc.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Complex networks en_US
dc.subject Modulus en_US
dc.subject Family of walks en_US
dc.subject Centrality en_US
dc.subject Graph theory en_US
dc.subject Clustering en_US
dc.title Complex network analysis using modulus of families of walks en_US
dc.type Dissertation en_US
dc.description.degree Doctor of Philosophy en_US
dc.description.level Doctoral en_US
dc.description.department Department of Electrical and Computer Engineering en_US
dc.description.advisor Pietro Poggi-Corradini en_US
dc.description.advisor Caterina M. Scoglio en_US
dc.date.published 2017 en_US
dc.date.graduationmonth May en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx


Advanced Search

Browse

My Account

Statistics








Center for the

Advancement of Digital

Scholarship

118 Hale Library

Manhattan KS 66506


(785) 532-7444

cads@k-state.edu