Doctoral Dissertations
Abstract
"Large scale networks are an indispensable part of our daily life; be it biological network, smart grids, academic collaboration networks, social networks, vehicular networks, or the networks as part of various smart environments, they are fast becoming ubiquitous. The successful realization of applications and services over them depend on efficient solution to their computational challenges that are compounded with network dynamics. The core challenges underlying large scale networks, for example: determining central (influential) nodes (and edges), interactions and contacts among nodes, are the basis behind the success of applications and services. Though at first glance these challenges seem to be trivial, the network characteristics affect their effective and efficient evaluation strategy. We thus propose to leverage large scale network structural characteristics and temporal dynamics in addressing these core conceptual challenges in this dissertation.
We propose a divide and conquer based computationally efficient algorithm that leverages the underlying network community structure for deterministic computation of betweenness centrality indices for all nodes. As an integral part of it, we also propose a computationally efficient agglomerative hierarchical community detection algorithm. Next, we propose a network structure evolution based novel probabilistic link prediction algorithm that predicts set of links occurring over subsequent time periods with higher accuracy. To best capture the evolution process and have higher prediction accuracy we propose multiple time scales with the Markov prediction model. Finally, we propose to capture the multi-periodicity of human mobility pattern with sinusoidal intensity function of a cascaded nonhomogeneous Poisson process, to predict the future contacts over mobile networks. We use real data set and benchmarked approaches to validate the better performance of our proposed approaches"--Abstract, page iii.
Advisor(s)
Das, Sajal K.
Committee Member(s)
Leopold, Jennifer
Jiang, Wei
Lin, Dan
Saifullah, Abusayeed
Çetinkaya, Egemen K.
Department(s)
Computer Science
Degree Name
Ph. D. in Computer Science
Sponsor(s)
National Science Foundation (U.S.)
Missouri University of Science and Technology. Intelligent Systems Center
Research Center/Lab(s)
Intelligent Systems Center
Publisher
Missouri University of Science and Technology
Publication Date
Fall 2017
Pagination
xi, 134 pages
Note about bibliography
Includes bibliographic references (pages 119-133)
Rights
© 2017 Sima Das, All rights reserved.
Document Type
Dissertation - Open Access
File Type
text
Language
English
Thesis Number
T 11217
Electronic OCLC #
1021857510
Recommended Citation
Das, Sima, "Efficient algorithms for analyzing large scale network dynamics: Centrality, community and predictability" (2017). Doctoral Dissertations. 2619.
https://scholarsmine.mst.edu/doctoral_dissertations/2619
Comments
Financial support of National Science Foundation (U.S.) CCF-1533918, CCF-1725755 and CBET-1609642