logo

SCIENCE CHINA Information Sciences, Volume 63, Issue 1: 112202(2020) https://doi.org/10.1007/s11432-019-9890-5

Asymptotic properties of distributed social sampling algorithm

More info
  • ReceivedJan 18, 2019
  • AcceptedApr 29, 2019
  • PublishedDec 23, 2019

Abstract

Social sampling is a novel randomized message passing protocol inspired by social communication for opinion formation in social networks. In a typical social sampling algorithm, each agent holds a sample from the empirical distribution of social opinions at initial time,and it collaborates with other agents in a distributed manner to estimate the initial empirical distribution by randomly sampling a message from current distribution estimate. In this paper, we focus on analyzing the theoretical properties of the distributed social sampling algorithm over random networks. First, we provide a framework based on stochastic approximation to study the asymptotic properties of the algorithm. Then, under mild conditions, we prove that the estimates of all agents converge to a common random distribution, which is composed of the initial empirical distribution and the accumulation of quantized error. Besides, by tuning algorithm parameters, we prove the strong consistency, namely, the distribution estimates of agents almost surely converge to the initial empirical distribution.Furthermore, the asymptotic normality of estimation error generated by distributed social sample algorithm is addressed. Finally, we provide a numerical simulation to validate the theoretical results of this paper.


Acknowledgment

This work was supported by National Key Research and Development Program of China (Grant No. 2016YFB0901900) and National Natural Science Foundation of China (Grant No. 61573345).


References

[1] Anderson B D O, Ye M. Recent Advances in the Modelling and Analysis of Opinion Dynamics on Influence Networks. Int J Autom Comput, 2019, 16: 129-149 CrossRef Google Scholar

[2] Flache A, M?s M, Feliciani T. Models of Social Influence: Towards the Next Frontiers. JASSS, 2017, 20 CrossRef Google Scholar

[3] Proskurnikov A V, Tempo R. A tutorial on modeling and analysis of dynamic social networks. Part I. Annu Rev Control, 2017, 43: 65-79 CrossRef Google Scholar

[4] Proskurnikov A V, Tempo R. A tutorial on modeling and analysis of dynamic social networks. Part II. Annu Rev Control, 2018, 45: 166-190 CrossRef Google Scholar

[5] Holley R A, Liggett T M. Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model. Ann Probab, 1975, 3: 643-663 CrossRef Google Scholar

[6] Acemoglu D, Dahleh M A, Lobel I. Bayesian Learning in Social Networks. Rev Economic Studies, 2011, 78: 1201-1236 CrossRef Google Scholar

[7] Narayanan H, Niyogi P. Language evolution, coalescent processes, and the consensus problem on a social network. J Math Psychology, 2014, 61: 19-24 CrossRef Google Scholar

[8] Xiao Y P, Li X X, Liu Y N. Correlations multiplexing for link prediction in multidimensional network spaces. Sci China Inf Sci, 2018, 61: 112103 CrossRef Google Scholar

[9] Friedkin N E, Proskurnikov A V, Tempo R. Network science on belief system dynamics under logic constraints. Science, 2016, 354: 321-326 CrossRef PubMed ADS Google Scholar

[10] Hegselmann R, Krause U. Opinion dynamics and bounded confidence models, analysis, and simulation. J Artif Soc Social Simulat, 2002, 5: 1--33. Google Scholar

[11] Zhang J, Hong Y. Opinion evolution analysis for short-range and long-range Deffuant-Weisbuch models. Physica A-Statistical Mech its Appl, 2013, 392: 5289-5297 CrossRef ADS Google Scholar

[12] Pineda M, Toral R, Hernández-García E. Noisy continuous-opinion dynamics. J Stat Mech, 2009, 2009(08): P08001 CrossRef ADS arXiv Google Scholar

[13] Boyd S, Ghosh A, Prabhakar B. Randomized gossip algorithms. IEEE Trans Inform Theor, 2006, 52: 2508-2530 CrossRef Google Scholar

[14] Lou Y, Strub M, Li D. Reference Point Formation in Social Networks, Wealth Growth, and Inequality. SSRN J, CrossRef Google Scholar

[15] Frasca P, Ishii H, Ravazzi C. Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation: A tutorial overview. Eur J Control, 2015, 24: 2-13 CrossRef Google Scholar

[16] Friedkin N E, Johnsen E C. Social influence networks and opinion change. Advances in Group Processes, 1999, 16: 1--29 没查到. Google Scholar

[17] Ravazzi C, Frasca P, Tempo R. Ergodic Randomized Algorithms and Dynamics Over Networks. IEEE Trans Control Netw Syst, 2015, 2: 78-87 CrossRef Google Scholar

[18] Acemoglu D, Bimpikis K, Ozdaglar A. Dynamics of information exchange in endogenous social networks. Theor Economics, 2014, 9: 41-97 CrossRef Google Scholar

[19] Acemo?lu D, Como G, Fagnani F. Opinion Fluctuations and Disagreement in Social Networks. Math OR, 2013, 38: 1-27 CrossRef Google Scholar

[20] Ceragioli F, Frasca P. Consensus and Disagreement: The Role of Quantized Behaviors in Opinion Dynamics. SIAM J Control Optim, 2018, 56: 1058-1080 CrossRef Google Scholar

[21] Sarwate A D, Javidi T. Distributed Learning of Distributions via Social Sampling. IEEE Trans Automat Contr, 2015, 60: 34-45 CrossRef Google Scholar

[22] Degroot M H. Reaching a Consensus. J Am Statistical Association, 1974, 69: 118-121 CrossRef Google Scholar

[23] Borkar V, Varaiya P P. Asymptotic agreement in distributed estimation. IEEE Trans Automat Contr, 1982, 27: 650-655 CrossRef Google Scholar

[24] Tsitsiklis J N, Athans M. Convergence and asymptotic agreement in distributed decision problems. IEEE Trans Automat Contr, 1984, 29: 42-50 CrossRef Google Scholar

[25] Olfati-Saber R, Murray R M. Consensus Problems in Networks of Agents With Switching Topology and Time-Delays. IEEE Trans Automat Contr, 2004, 49: 1520-1533 CrossRef Google Scholar

[26] Kar S, Moura J M F. Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise. IEEE Trans Signal Process, 2009, 57: 355-369 CrossRef ADS Google Scholar

[27] Huang M, Manton J H. Coordination and Consensus of Networked Agents with Noisy Measurements: Stochastic Algorithms and Asymptotic Behavior. SIAM J Control Optim, 2009, 48: 134-161 CrossRef Google Scholar

[28] Fang H, Chen H F, Wen L. On control of strong consensus for networked agents with noisy observations. J Syst Sci Complex, 2012, 25: 1-12 CrossRef Google Scholar

[29] LeBlanc H J, Zhang H, Koutsoukos X. Resilient Asymptotic Consensus in Robust Networks. IEEE J Sel Areas Commun, 2013, 31: 766-781 CrossRef Google Scholar

[30] Zong X F, Li T, Zhang J F. Consensus conditions of continuous-time multi-agent systems with time-delays and measurement noises. Automatica, 2019, 99: 412-419 CrossRef Google Scholar

[31] Zong X F, Li T, Zhang J F. Consensus Conditions of Continuous-Time Multi-Agent Systems with Additive and Multiplicative Measurement Noises. SIAM J Control Optim, 2018, 56: 19-52 CrossRef Google Scholar

[32] Wang Y H, Lin P, Hong Y G. Distributed regression estimation with incomplete data in multi-agent networks. Sci China Inf Sci, 2018, 61: 092202 CrossRef Google Scholar

[33] Rajagopal R, Wainwright M J. Network-Based Consensus Averaging With General Noisy Channels. IEEE Trans Signal Process, 2011, 59: 373-385 CrossRef ADS Google Scholar

[34] Meyer C D. Matrix Analysis and Applied Linear Algebra. Philadelphia: SIAM, 2000. Google Scholar

[35] Durrett R. Probability Theory and Examples. Camberidge: Camberidge Press, 2010. Google Scholar

[36] Chen H F. Stochastic Approximation and Its Applications. New York: Kluwer Academic Publishers, 2003. Google Scholar

  • Figure 1

    (Color online) Trace of estimate of $Q_{i,k}$ for $i\in~\left[~N\right]$ over every single opinion state $m\in\left[~M\right]$ with $M=4$. protectłinebreak (a) $m=1$, the estimate of the first element of true empirical distribution $q^{\ast}$; (b) $m=2$, the estimate of the second element of $q^{\ast}$; (c) $m=3$, the estimate of the third element of $q^{\ast}$; (d) $m=4$, the estimate of the last element of $q^{\ast}$.

  • Figure 2

    (Color online) Histogram and limit distribution for $\left(~Q_{i,k}-q^{\ast}\right)/\sqrt{\delta_{k}}$ at $k=500$. (a) Node 5; (b) node 6; protectłinebreak (c) node 10; (d) node 24.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1