Clustering, coverage and aggregation methods for large networks

Xu, Yunwen

Permalink

https://hdl.handle.net/2142/72930 Copy

Description

Title

Clustering, coverage and aggregation methods for large networks

Author(s)

Xu, Yunwen

Issue Date

2015-01-21

Director of Research (if dissertation) or Advisor (if thesis)

Beck, Carolyn

Doctoral Committee Chair(s)

Beck, Carolyn

Committee Member(s)

• Salapaka, Srinivasa M.
• Srikant, Rayadurgam
• Mehta, Prashant
• Olshevsky, Alex

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Clustering
• Maximum Entropy Principle
• Dynamic Coverage Control
• Deterministic Annealing

Abstract

The work in this thesis presents methods for clustering and aggregation of large dynamic networked systems, typically consisting of numerous units/subsystems with complex interactions. Networked system models are used in many scientific and real world applications, for example to describe functional relationships among neurons in the brain, to achieve consensus in the design of communication and controller actuation rules in multi-agent systems, and to estimate multiple service demands in web-based software systems in order to enhance service quality by web cluster relocation. The level of complexity in modeling, analysis, and control synthesis for these systems increases combinatorially with the number of constituent elements in the network. This thesis presents methods for obtaining concise aggregated representations of such systems, while capturing important and relevant interconnectivity information. In the first part of this thesis, we develop a theoretical framework for aggregating systems that are represented by directed weighted graphs. In this framework, we formulate an optimization problem, with the goal of minimizing a dissimilarity function that captures the distance between the representative and the original graphs. We propose a class of dissimilarity measures and introduce the notion of composite graph sets allowing us to compare directed weighted graphs that contain different numbers of nodes. The dissimilarity measures capture node similarities based on node connectivity, and in the simplest case reduce to metrics previously defined for equal-sized undirected unweighted graphs. The representative graph is determined by systematically identifying and aggregating similar nodes of the original graph into supernodes, and then determining the inter supernode connectivities. The key challenge herein is in overcoming the computational complexity that arises in iteratively solving two combinatorial optimization problems corresponding to evaluating and minimizing the cost function (dissimilarity measure). In our formulation, using the composite graph sets, only a single optimization problem is needed in every iteration. Further, we introduce a maximum entropy based soft aggregation approach for node clustering, and propose a multi-scaled aggregation method whose central part incorporates the Deterministic Annealing algorithm. Specifically, we solve a sequence of relaxed minimization problems by allowing soft cluster associations; as we gradually decrease the level of softness, the solution for the original problem is approached. We discuss graph structures for which this aggregation method is provably effective, and provide comprehensive simulation examples demonstrating this efficacy. As a special case, we study the reduction of Markov chains. By viewing a Markov chain as a directed weighted graph, the graph aggregation techniques we propose are directly applicable. If we consider nearly completely decomposable Markov chains, that is, chains whose transition matrices P can be written as a perturbation added to a completely decomposable (reducible) chain P*, i.e., P = P* + eC, then we provide sufficient conditions under which our method guarantees recovery of the decomposable sub-chain structure indicated by P*, thus yielding easily verifiable conditions to corroborate results given by perturbation theory. We then derive upper bound on how close the stationary distribution of aggregated Markov chain is to the aggregated stationary distribution of the original Markov chain. The effectiveness of this method has been demonstrated through numerous examples at a variety of scales. We further apply this aggregation method to reduce systems consisting of interactive stochastic processes that can be represented by graph models. In particular, we study seismic activities at different geological locations, with parametric generative models characterizing the influences among every location. In this scenario, ensemble interactions within the system can be discovered by clustering the underlying graph model. In the second part of this thesis, we consider dynamic clustering and coverage problems. The goal is to use a small number of resources to provide continuous and sufficient coverage for a large number of moving objects. We integrate control-theoretic methods, specifically Lyapunov-based analysis, into our aggregation framework. Specifically, we adaptively compute the actuation rules for all resources to achieve the tracking objective, in addition to a set of optimal resource locations for fixed time-instances. For systems where moving objects are driven by acceleration fields, we show that a dynamic control is necessary to achieve dynamic coverage, and provide closed-form solutions for the resource dynamics. The algorithms we propose guarantee asymptotic tracking of cluster group dynamics, and we further establish continuity and boundedness of the corresponding control laws. The algorithm has been successfully applied to many systems with a large number of dynamic sites, and we provide examples in this thesis to corroborate the results.

Graduation Semester

2014-12

Permalink

http://hdl.handle.net/2142/72930

Copyright and License Information

Copyright 2014 Yunwen Xu

Owning Collections