Graph methods in Multi Agent Systems Coordination and Social Network Analysis

In this thesis several results on two main topics are collected: the coordination of networked multi agents systems and the diffusion of innovation of social networks. The results are organized in two parts, each one related with one of the two main topics. The common aspect of all the presented problems is the following: all the system are represented by graphs. Two are the main contributions of the first part. • A formation control strategy, based on gossip, which leads a set of autonomous vehicles to converge to a desired spatial disposition in absence of a common reference frame. If the vehicles have common direction, we prove that the proposed algorithm is robust against noise on displacement measurement. • \item The formalization of the Heterogeneous Multi Vehicle Routing Problem, which can be described as follows: given an heterogeneous set of mobile robots, and a set of task to be served randomly displaced in a 2D environment, find the optimal task assignment to minimize the service cost. We firstly characterize the optimal centralized solution, and then we propose two distributed algorithms, based on gossip, which lead the system to a sub-optimal solutions and are significantly computationally more efficient than the optimal one. The contributions of the second part are the following. • We study how the innovation spreads in a Social Network according to the so called Linear Threshold Model, in which the innovation is incepted in the network starting from a seed set, and nodes adopt the innovation if the ratio of the neighbours that have already adopted it is greater than or equal a certain threshold value. We focus on the cohesive subset of the network, which can be used to compute the set of final adopters. If a set is cohesive and none of the nodes have adopted the innovation at a certain time $t$, then they are not able to adopt the innovation at any $t'>t$. We propose an algorithm based on linear programming which computes the maximal cohesive subset of the complement of the seed set. • According to the Linear Threshold Model, we define two problem of interest in Social Networks analysis and characterize the optimal solution: the Influence Maximization Problem in Finite Time and the diffusion of innovation over a target set. • We characterize the novel Non Progressive Linear Threshold Model, which extends the classical Linear Threshold Model. We formalize the model and we give a characterization of the network dynamics in terms of cohesive and persistent sets