Abstract
We study the convergence of influence networks, where each node changes its state according to the majority of its neighbors. Our main result is a new Ω(n 2/log2 n) bound on the convergence time in the synchronous model, solving the classic “Democrats and Republicans” problem. Furthermore, we give a bound of Θ(n 2) for the sequential model in which the sequence of steps is given by an adversary and a bound of Θ(n) for the sequential model in which the sequence of steps is given by a benevolent process.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A Biological Solution to a Fundamental Distributed Computing Problem. Science, 183–185 (2011)
Adler, F.R., Gordon, D.M.: Information Collection and Spread by Networks of Patrolling Ants. The American Naturalist, 373–400 (1992)
Asuncion, A.U., Goodrich, M.T.: Turning Privacy Leaks into Floods: Surreptitious Discovery of Social Network Friendships and Other Sensitive Binary Attribute Vectors. In: Workshop on Privacy in the Electronic Society (WPES), pp. 21–30 (2010)
Avin, C., Lotker, Z., Pignolet, Y.A.: On The Elite of Social Networks. In: Personal Communication (2012)
Brin, S., Page, L.: The Anatomy of a Large-Scale Hypertextual Web Search Engine. In: Seventh International World-Wide Web Conference, WWW (1998)
Bickson, D., Tock, Y., Zymnis, A., Boyd, S.P., Dolev, D.: Distributed Large Scale Network Utility Maximization. In: International Conference on Symposium on Information Theory, ISIT (2009)
Chen, W., Yuan, Y., Zhang, L.: Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In: Industrial Conference on Data Mining (ICDM), pp. 88–97 (2010)
Doerr, B., Fouz, M., Friedrich, T.: Social Networks Spread Rumors in Sublogarithmic Time. In: Symposium on Theory of Computing (STOC), pp. 21–30 (2011)
Floréen, P., Kaski, P., Polishchuk, V., Suomela, J.: Brief Announcement: Distributed Almost Stable Marriage. In: Principles of Distributed Computing (PODC), pp. 281–282 (2010)
Fruchterman, T.M.J., Reingold, E.M.: Graph Drawing by Force-Directed Placement. In: Software: Practice and Experience, pp. 1129–1164 (1991)
Gardner, M.: Mathematical Games: The Fantastic Combinations of John Conway’s new Solitaire Game “Life”. Scientific American, 120–123 (1970)
Goles, E., Olivos, J.: Periodic Behaviour of Generalized Threshold Functions. Discrete Mathematics, 187–189 (1980)
Gale, D., Shapley, L.S.: College Admissions and the Stability of Marriage. The American Mathematical Monthly, 9–15 (1962)
Goles, E., Tchuente, M.: Iterative Behaviour of Generalized Majority Functions. In: Mathematical Social Sciences, pp. 197–204 (1983)
Heider, F.: Attitudes and Cognitive Organization. Journal of Psychology, 107–112 (1946)
Hoefer, M.: Local Matching Dynamics in Social Networks. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 113–124. Springer, Heidelberg (2011)
Kelman, H.C.: Compliance, Identification, and Internalization: Three Processes of Attitude Change. Journal of Conflict Resolution, 51–60 (1958)
Kamada, T., Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 7–15 (1989)
Kempe, D., Kleinberg, J.M., Tardos, É.: Influential Nodes in a Diffusion Model for Social Networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1127–1138. Springer, Heidelberg (2005)
Kleinberg, J.M.: Hubs, Authorities, and Communities. ACM Computing Surveys, CSUR (1999)
Kohonen, T.: Self-Organization and Associative Memory. Springer (1989)
Kostka, J., Oswald, Y.A., Wattenhofer, R.: Word of mouth: Rumor dissemination in social networks. In: Shvartsman, A.A., Felber, P. (eds.) SIROCCO 2008. LNCS, vol. 5058, pp. 185–196. Springer, Heidelberg (2008)
Kipnis, A., Patt-Shamir, B.: On the Complexity of Distributed Stable Matching with Small Messages. Distributed Computing, 151–161 (2010)
Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized Rumor Spreading. In: Foundations of Computer Science, FOCS (2000)
Kaufmann, M., Wagner, D.: Drawing Graphs: methods and models. Springer (2001)
Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Signed Networks in Social Media. In: Conference on Human Factors in Computing Systems (CHI), pp. 1361–1370 (2010)
Leskovec, J., Singh, A., Kleinberg, J.M.: Patterns of Influence in a Recommendation Network. In: Ng, W.-K., Kitsuregawa, M., Li, J., Chang, K. (eds.) PAKDD 2006. LNCS (LNAI), vol. 3918, pp. 380–389. Springer, Heidelberg (2006)
Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and Analysis of Online Social Networks. In: 7th ACM SIGCOMM Conference on Internet Measurement, pp. 29–42 (2007)
Von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press (1966)
Nagel, K., Schreckenberg, M.: A Cellular Automaton Model for Freeway Traffic. Journal de Physique I, 2221–2229 (1992)
Pearl, J.: Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach. In: Second National Conference on Artificial Intelligence (AAAI), pp. 133–136 (1982)
Poljak, S., Sra, M.: On Periodical Behaviour in Societies with Symmetric Influences. Combinatorica, 119–121 (1983)
Rolls, E.T., Treves, A.: Neural Networks and Brain Function. Oxford University Press, USA (1998)
Sauerwald, T., Sudholt, D.: A Self-Stabilizing Algorithm for Cut Problems in Synchronous Networks. Theoretical Computer Science, 1599–1612 (2010)
Sauerwald, T., Stauffer, A.: Rumor Spreading and Vertex Expansion on Regular Graphs. In: Symposium on Discrete Algorithms (SODA), pp. 462–475 (2011)
Watts, D.J.: A Simple Model of Global Cascades on Random Networks. Proceedings of the National Academy of Sciences, 5766–5771 (2002)
Winkler, P.: Puzzled: Delightful Graph Theory. Communications of the ACM, 104 (2008)
Wolfram, S.: A New Kind of Science. Wolfram Media (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frischknecht, S., Keller, B., Wattenhofer, R. (2013). Convergence in (Social) Influence Networks. In: Afek, Y. (eds) Distributed Computing. DISC 2013. Lecture Notes in Computer Science, vol 8205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41527-2_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-41527-2_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41526-5
Online ISBN: 978-3-642-41527-2
eBook Packages: Computer ScienceComputer Science (R0)