BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Fabio Fagnani

Fabio Fagnani appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Systems and Controlmath.OCSocial and Information Networksmath.PRMultiagent SystemsComputer Science and Game Theorymath.DSDiscrete Mathematicseess.SYInformation Theorymath.APmath.ITphysics.soc-phq-fin.MF

Catalog footprint

What is connected

26works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

26 published item(s)

preprint2022arXiv

Targeting interventions for displacement minimization in opinion dynamics

Social influence is largely recognized as a key factor in opinion formation processes. Recently, the role of external forces in inducing opinion displacement and polarization in social networks has attracted significant attention. This is in particular motivated by the necessity to understand and possibly prevent interference phenomena during political campaigns and elections. In this paper, we formulate and solve a targeted intervention problem for opinion displacement minimization on a social network. Specifically, we consider a min-max problem whereby a social planner (the defender) aims at selecting the optimal network intervention within her given budget constraint in order to minimize the opinion displacement in the system that an adversary (the attacker) is instead trying to maximize. Our results show that the optimal intervention of the defender has two regimes. For large enough budget, the optimal intervention of the social planner acts on all nodes proportionally to a new notion of network centrality. For lower budget values, such optimal intervention has a more delicate structure and is rather concentrated on a few target individuals.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Equilibria and Systemic Risk in Saturated Networks

We undertake a fundamental study of network equilibria modeled as solutions of fixed point equations for monotone linear functions with saturation nonlinearities. The considered model extends one originally proposed to study systemic risk in networks of financial institutions interconnected by mutual obligations and is one of the simplest continuous models accounting for shock propagation phenomena and cascading failure effects. It also characterizes Nash equilibria of constrained quadratic network games with strategic complementarities. We first derive explicit expressions for network equilibria and prove necessary and sufficient conditions for their uniqueness encompassing and generalizing results available in the literature. Then, we study jump discontinuities of the network equilibria when the exogenous flows cross certain regions of measure 0 representable as graphs of continuous functions. Finally, we discuss some implications of our results in the two main motivating applications. In financial networks, this bifurcation phenomenon is responsible for how small shocks in the assets of a few nodes can trigger major aggregate losses to the system and cause the default of several agents. In constrained quadratic network games, it induces a blow-up behavior of the sensitivity of Nash equilibria with respect to the individual benefits.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast Spread in Controlled Evolutionary Dynamics

We study the spread of a novel state in a network, in the presence of an exogenous control. The considered controlled evolutionary dynamics is a non-homogeneous Markov process that describes the evolution of the states of all nodes in the network. Through a rigorous analysis, we estimate the performance of the system by establishing upper and lower bounds on the expected time needed for the novel state to replace the original one. Such bounds are expressed in terms of the support and intensity of the control policy (specifically, the set of nodes that can be controlled and its energy) and of the network topology and establish fundamental limitations on the system's performance. Leveraging these results, we are able to classify network structures depending on the possibility to control the system using simple open-loop control policies. Finally, we propose a feedback control policy that, using little knowledge of the network topology and of the system's evolution at a macroscopic level, allows for a substantial speed up of the spreading process with respect to simple open-loop control policies. All these theoretical results are presented together with explanatory examples, for which Monte Carlo simulations corroborate our analytical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graphical Games and Decomposition

We consider graphical games as introduced by Kearns et al. (2001). First we analyse the interaction of graphicality with a notion of strategic equivalence of games, providing a minimal complexity graphical description for games. Then we study the interplay between graphicality and the classical decomposition of games proposed by Candogan et al. (2011), characterizing the graphical properties of each part of the decomposition.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On a Centrality Maximization Game

The Bonacich centrality is a well-known measure of the relative importance of nodes in a network. This notion is, for example, at the core of Google's PageRank algorithm. In this paper we study a network formation game where each player corresponds to a node in the network to be formed and can decide how to rewire his m out-links aiming at maximizing his own Bonacich centrality, which is his utility function. We study the Nash equilibria (NE) and the best response dynamics of this game and we provide a complete classification of the set of NE when m=1 and a fairly complete classification of the NE when m=2. Our analysis shows that the centrality maximization performed by each node tends to create undirected and disconnected or loosely connected networks, namely 2-cliques for m=1 and rings or a special "Butterfly"-shaped graph when m=2. Our results build on locality property of the best response function in such game that we formalize and prove in the paper.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimal Targeting in Super-Modular Games

We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm with provable convergence properties for its solution. We discuss in detail the special case of network coordination games and its relation with the notion of cohesiveness. Finally, we show with simulations the strength of our approach with respect to naive heuristics based on classical network centrality measures.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robustness of Nash Equilibria in Network Games

We analyze the robustness of (pure strategy) Nash equilibria for network games against perturbations of the players' utility functions. We first derive a simple characterization of the margin of robustness, defined as the minimum magnitude of a perturbation that makes a Nash equilibrium of the original game stop being so in the perturbed game. Then, we investigate what the maximally robust equilibria are in some standard network games such as the coordination and the anti-coordination game. Finally, as an application, we provide some sufficient conditions for the existence of Nash equilibria in network games with a mixture of coordinating and anticoordinating games.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

On stochastic imitation dynamics in large-scale networks

We consider a broad class of stochastic imitation dynamics over networks, encompassing several well known learning models such as the replicator dynamics. In the considered models, players have no global information about the game structure: they only know their own current utility and the one of neighbor players contacted through pairwise interactions in a network. In response to this information, players update their state according to some stochastic rules. For potential population games and complete interaction networks, we prove convergence and long-lasting permanence close to the evolutionary stable strategies of the game. These results refine and extend the ones known for deterministic imitation dynamics as they account for new emerging behaviors including meta-stability of the equilibria. Finally, we discuss extensions of our results beyond the fully mixed case, studying imitation dynamics where agents interact on complex communication networks.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

On imitation dynamics in potential population games

Imitation dynamics for population games are studied and their asymptotic properties analyzed. In the considered class of imitation dynamics - that encompass the replicator equation as well as other models previously considered in evolutionary biology - players have no global information about the game structure, and all they know is their own current utility and the one of fellow players contacted through pairwise interactions. For potential population games, global asymptotic stability of the set of Nash equilibria of the sub-game restricted to the support of the initial population configuration is proved. These results strengthen (from local to global asymptotic stability) existing ones and generalize them to a broader class of dynamics. The developed techniques highlight a certain structure of the problem and suggest possible generalizations from the fully mixed population case to imitation dynamics whereby agents interact on complex communication networks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A game theoretic approach to a peer-to-peer cloud storage model

Classical cloud storage based on external data providers has been recognized to suffer from a number of drawbacks. This is due to its inherent centralized architecture which makes it vulnerable to external attacks, malware, technical failures, as well to the large premium charged for business purposes. In this paper, we propose an alternative distributed peer-to-peer cloud storage model which is based on the observation that the users themselves often have available storage capabilities to be offered in principle to other users. Our set-up is that of a network of users connected through a graph, each of them being at the same time a source of data to be stored externally and a possible storage resource. We cast the peer-to-peer storage model to a Potential Game and we propose an original decentralized algorithm which makes units interact, cooperate, and store a complete back up of their data on their connected neighbors. We present theoretical results on the algorithm as well a good number of simulations which validate our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Diffusion of innovation in large scale graphs

Will a new smartphone application diffuse deeply in the population or will it sink into oblivion soon? To predict this, we argue that common models of spread of innovations based on cascade dynamics or epidemics may not be fully adequate. Therefore we propose a novel stochastic network dynamics modeling the spread of a new technological asset, whose adoption is based on the word-of-mouth and the persuasion strength increases the more the product is diffused. In this paper we carry on an analysis on large scale graphs to show off how the parameters of the model, the topology of the graph and, possibly, the initial diffusion of the asset, determine whether the spread of the asset is successful or not. In particular, by means of stochastic dominations and deterministic approximations, we provide some general results for a large class of expansive graphs. Finally we present numerical simulations trying to expand the analytical results we proved to even more general topologies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

From local averaging to emergent global behaviors: the fundamental role of network interconnections

Distributed averaging is one of the simplest and most studied network dynamics. Its applications range from cooperative inference in sensor networks, to robot formation, to opinion dynamics. A number of fundamental results and examples scattered through the literature are gathered here and originally presented, emphasizing the deep interplay between the network interconnection structure and the emergent global behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Threshold models of cascades in large-scale networks

The spread of new beliefs, behaviors, conventions, norms, and technologies in social and economic networks are often driven by cascading mechanisms, and so are contagion dynamics in financial networks. Global behaviors generally emerge from the interplay between the structure of the interconnection topology and the local agents' interactions. We focus on the Linear Threshold Model (LTM) of cascades first introduced by Granovetter (1978). This can be interpreted as the best response dynamics in a network game whereby agents choose strategically between two actions and their payoff is an increasing function of the number of their neighbors choosing the same action. Each agent is equipped with an individual threshold representing the number of her neighbors who must have adopted a certain action for that to become the agent's best response. We analyze the LTM dynamics on large-scale networks with heterogeneous agents. Through a local mean-field approach, we obtain a nonlinear, one-dimensional, recursive equation that approximates the evolution of the LTM dynamics on most of the networks of a given size and distribution of degrees and thresholds. Specifically, we prove that, on all but a fraction of networks with given degree and threshold statistics that is vanishing as the network size grows large, the actual fraction of adopters of a given action in the LTM dynamics is arbitrarily close to the output of the aforementioned recursion. We then analyze the dynamic behavior of this recursion and its bifurcations from a dynamical systems viewpoint. Applications of our findings to some real network testbeds show good adherence of the theoretical predictions to numerical simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Average resistance of toroidal graphs

The average effective resistance of a graph is a relevant performance index in many applications, including distributed estimation and control of network systems. In this paper, we study how the average resistance depends on the graph topology and specifically on the dimension of the graph. We concentrate on $d$-dimensional toroidal grids and we exploit the connection between resistance and Laplacian eigenvalues. Our analysis provides tight estimates of the average resistance, which are key to study its asymptotic behavior when the number of nodes grows to infinity. In dimension two, the average resistance diverges: in this case, we are able to capture its rate of growth when the sides of the grid grow at different rates. In higher dimensions, the average resistance is bounded uniformly in the number of nodes: in this case, we conjecture that its value is of order $1/d$ for large $d$. We prove this fact for hypercubes and when the side lengths go to infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Robustness of large-scale stochastic matrices to localized perturbations

Upper bounds are derived on the total variation distance between the invariant distributions of two stochastic matrices differing on a subset W of rows. Such bounds depend on three parameters: the mixing time and the minimal expected hitting time on W for the Markov chain associated to one of the matrices; and the escape time from W for the Markov chain associated to the other matrix. These results, obtained through coupling techniques, prove particularly useful in scenarios where W is a small subset of the state space, even if the difference between the two matrices is not small in any norm. Several applications to large-scale network problems are discussed, including robustness of Google's PageRank algorithm, distributed averaging and consensus algorithms, and interacting particle systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The robustness of democratic consensus

In linear models of consensus dynamics, the state of the various agents converges to a value which is a convex combination of the agents' initial states. We call it democratic if in the large scale limit (number of agents going to infinity) the vector of convex weights converges to 0 uniformly. Democracy is a relevant property which naturally shows up when we deal with opinion dynamic models and cooperative algorithms such as consensus over a network: it says that each agent's measure/opinion is going to play a negligeable role in the asymptotic behavior of the global system. It can be seen as a relaxation of average consensus, where all agents have exactly the same weight in the final value, which becomes negligible for a large number of agents.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Message passing optimization of Harmonic Influence Centrality

This paper proposes a new measure of node centrality in social networks, the Harmonic Influence Centrality, which emerges naturally in the study of social influence over networks. Using an intuitive analogy between social and electrical networks, we introduce a distributed message passing algorithm to compute the Harmonic Influence Centrality of each node. Although its design is based on theoretical results which assume the network to have no cycle, the algorithm can also be successfully applied on general graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Limited benefit of cooperation in distributed relative localization

Important applications in robotic and sensor networks require distributed algorithms to solve the so-called relative localization problem: a node-indexed vector has to be reconstructed from measurements of differences between neighbor nodes. In a recent note, we have studied the estimation error of a popular gradient descent algorithm showing that the mean square error has a minimum at a finite time, after which the performance worsens. This paper proposes a suitable modification of this algorithm incorporating more realistic "a priori" information on the position. The new algorithm presents a performance monotonically decreasing to the optimal one. Furthermore, we show that the optimal performance is approximated, up to a 1 + \eps factor, within a time which is independent of the graph and of the number of nodes. This convergence time is very much related to the minimum exhibited by the previous algorithm and both lead to the following conclusion: in the presence of noisy data, cooperation is only useful till a certain limit.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A distributed classification/estimation algorithm for sensor networks

In this paper, we address the problem of simultaneous classification and estimation of hidden parameters in a sensor network with communications constraints. In particular, we consider a network of noisy sensors which measure a common scalar unknown parameter. We assume that a fraction of the nodes represent faulty sensors, whose measurements are poorly reliable. The goal for each node is to simultaneously identify its class (faulty or non-faulty) and estimate the common parameter. We propose a novel cooperative iterative algorithm which copes with the communication constraints imposed by the network and shows remarkable performance. Our main result is a rigorous proof of the convergence of the algorithm and a characterization of the limit behavior. We also show that, in the limit when the number of sensors goes to infinity, the common unknown parameter is estimated with arbitrary small error, while the classification error converges to that of the optimal centralized maximum likelihood estimator. We also show numerical results that validate the theoretical analysis and support their possible generalization. We compare our strategy with the Expectation-Maximization algorithm and we discuss trade-offs in terms of robustness, speed of convergence and implementation simplicity.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Opinion fluctuations and disagreement in social networks

We study a tractable opinion dynamics model that generates long-run disagreements and persistent opinion fluctuations. Our model involves an inhomogeneous stochastic gossip process of continuous opinion dynamics in a society consisting of two types of agents: regular agents, who update their beliefs according to information that they receive from their social neighbors; and stubborn agents, who never update their opinions. When the society contains stubborn agents with different opinions, the belief dynamics never lead to a consensus (among the regular agents). Instead, beliefs in the society fail to converge almost surely, the belief profile keeps on fluctuating in an ergodic fashion, and it converges in law to a non-degenerate random vector. The structure of the network and the location of the stubborn agents within it shape the opinion dynamics. The expected belief vector evolves according to an ordinary differential equation coinciding with the Kolmogorov backward equation of a continuous-time Markov chain with absorbing states corresponding to the stubborn agents and converges to a harmonic vector, with every regular agent's value being the weighted average of its neighbors' values, and boundary conditions corresponding to the stubborn agents'. Expected cross-products of the agents' beliefs allow for a similar characterization in terms of coupled Markov chains on the network. We prove that, in large-scale societies which are highly fluid, meaning that the product of the mixing time of the Markov chain on the graph describing the social network and the relative size of the linkages to stubborn agents vanishes as the population size grows large, a condition of \emph{homogeneous influence} emerges, whereby the stationary beliefs' marginal distributions of most of the regular agents have approximately equal first and second moments.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Scaling limits for continuous opinion dynamics systems

Scaling limits are analyzed for stochastic continuous opinion dynamics systems, also known as gossip models. In such models, agents update their vector-valued opinion to a convex combination (possibly agent- and opinion-dependent) of their current value and that of another observed agent. It is shown that, in the limit of large agent population size, the empirical opinion density concentrates, at an exponential probability rate, around the solution of a probability-measure-valued ordinary differential equation describing the system's mean-field dynamics. Properties of the associated initial value problem are studied. The asymptotic behavior of the solution is analyzed for bounded-confidence opinion dynamics, and in the presence of an heterogeneous influential environment.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Broadcast gossip averaging algorithms: interference and asymptotical error in large networks

In this paper we study two related iterative randomized algorithms for distributed computation of averages. The first one is the recently proposed Broadcast Gossip Algorithm, in which at each iteration one randomly selected node broadcasts its own state to its neighbors. The second algorithm is a novel de-synchronized version of the previous one, in which at each iteration every node is allowed to broadcast, with a given probability: hence this algorithm is affected by interference among messages. Both algorithms are proved to converge, and their performance is evaluated in terms of rate of convergence and asymptotical error: focusing on the behavior for large networks, we highlight the role of topology and design parameters on the performance. Namely, we show that on fully-connected graphs the rate is bounded away from one, whereas the asymptotical error is bounded away from zero. On the contrary, on a wide class of locally-connected graphs, the rate goes to one and the asymptotical error goes to zero, as the size of the network grows larger.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deconvolution of linear systems with quantized input: an information theoretic viewpoint

In spite of the huge literature on deconvolution problems, very little is done for hybrid contexts where signals are quantized. In this paper we undertake an information theoretic approach to the deconvolution problem of a simple integrator with quantized binary input and sampled noisy output. We recast it into a decoding problem and we propose and analyze (theoretically and numerically) some low complexity on-line algorithms to achieve deconvolution.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The asymptotical error of broadcast gossip averaging algorithms

In problems of estimation and control which involve a network, efficient distributed computation of averages is a key issue. This paper presents theoretical and simulation results about the accumulation of errors during the computation of averages by means of iterative "broadcast gossip" algorithms. Using martingale theory, we prove that the expectation of the accumulated error can be bounded from above by a quantity which only depends on the mixing parameter of the algorithm and on few properties of the network: its size, its maximum degree and its spectral gap. Both analytical results and computer simulations show that in several network topologies of applicative interest the accumulated error goes to zero as the size of the network grows large.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Gossip consensus algorithms via quantized communication

This paper considers the average consensus problem on a network of digital links, and proposes a set of algorithms based on pairwise ''gossip'' communications and updates. We study the convergence properties of such algorithms with the goal of answering two design questions, arising from the literature: whether the agents should encode their communication by a deterministic or a randomized quantizer, and whether they should use, and how, exact information regarding their own states in the update.

0 citations0 reviewsNo code linkedOpen access