| dc.description.abstract | Knowing how important a node or an edge is, within a network, can be very valuable, for instance, in identifying those who are susceptible to malicious attacks, those who are bottlenecks to network performances, and those who are better suited as leaders, so that preventive measures may be taken, resources may be properly allocated, and roles may be properly assigned.
In this dissertation, we develop a novel collection of scalable distributed algorithms, which enable nodes in a large-scale network to cooperatively learn how important they are individually, with only local interaction and without any global coordination nor knowledge of the network topology. The node importance, or criticality, will be measured using the most fundamental centrality measures from the area of complex networks, namely, the betweenness centrality, closeness centrality, as well as a subset of their variations—those regarded by the network science community to be most fundamental that we believe are distributedly computable using a dynamical systems approach—so that insights gained in computing them shed light on how to compute other measures of similar nature.
The algorithms are developed based on tools and ideas from dynamical systems, graph theory, and network science. For each centrality measure, we first introduce some variables with graph-theoretic meaning, and expressed each measure as a function of these variables. Afterwards, we derive a set of equality and inequality constraints on these variables that characterize each centrality measure in lieu of its original definition. Every constraint involves only variables that are associated with neighboring nodes, so that neighboring nodes can check whether they are satisfied. Therefore, all of these constraints are distributed in nature.
Next, we use these constraints to develop a scalable distributed algorithm, which enables nodes in a network to cooperatively estimate their individual centrality with only local interaction and without any centralized coordination, nor high memory usages. Specifically, for tree graphs, the introduced variables are linearly and non-singularly related. Thus, by turning these constraints into a state equation, and the centrality measure function into an output equation, we subsequently obtain a networked dynamical system describing a distributed algorithm. For general graphs, the constraints we have discovered are necessary but insufficient, so the problem cannot be solved exactly. Therefore, we formulate a distributed optimization problem, a regularized linear program to estimate the centrality measures over the network by using a gradient method. Taking the gradient of the objective function with respect to the optimization variables, we obtain a scalable continuous-time distributed algorithm.
Moreover, for tree graphs, we show that each algorithm is a networked dynamical system, whose affine state equation has a unique equilibrium point that is always exponentially or finite-time stable, and whose output equation at the equilibrium point always yields the unknown centrality measure, thereby solving the problem. For general graphs, we evaluate the performance of the algorithm via extensive simulation, showing that it yields fairly accurate estimates in terms of ordering, on random geometric, Erdos-Renyi, and Barabasi-Albert graphs.
Finally, we experiment our algorithms for estimating node and edge betweenness centralities on both computer generated graphs and real networks for community detection and information spreading. We also propose a method for better spreading with the knowledge of community structures. The method using estimated betweenness performs very well in almost all scenarios. | en_US |
