Doctor of Philosophy / Department of Electrical and Computer Engineering / Pietro Poggi-Corradini / Caterina M. Scoglio / The modulus of a family of walks quanti es 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 e ective conductance centrality. After reinterpreting this measure in terms
of modulus of families of walks, we introduce a modi cation called shell modulus centrality,
that relies on the egocentric structure of the graph. Ego networks are networks formed
around egos with a speci c order of neighborhoods. We then propose e cient 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 bene ts from e cient algorithms for nding shortest loops, thus
we propose a deterministic combinatorial algorithm that nds a shortest cycle in graphs. The
proposed algorithm reduces the worst case time complexity of the existing combinatorial
algorithms to O(nm) or O(hkin2 log n) while visiting at most m - n + 1 cycles (size of
cycle basis). For most empirical networks with average degree in O(n1 ) our algorithm is
subcubic.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/35525 |
| Date | January 1900 |
| Creators | Shakeri, Heman |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0114 seconds