Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-04T19:05:11.207Z Has data issue: false hasContentIssue false
  • English
  • Français

Multi-level dynamo and opinion spreading†

Published online by Cambridge University Press:  06 May 2015

SARA BRUNETTI ,
GENNARO CORDASCO ,
ELENA LODI ,
LUISA GARGANO  and
WALTER QUATTROCIOCCHI
SARA BRUNETTI
Affiliation:
Department of Mathematics and Computer Science, University of Siena, 53100 Siena, Italy Email: [email protected], [email protected], [email protected]
GENNARO CORDASCO
Affiliation:
Dipartimento di Psicologia, Second University of Naples, 81100 Caserta, Italy Email: [email protected]
ELENA LODI
Affiliation:
Department of Mathematics and Computer Science, University of Siena, 53100 Siena, Italy Email: [email protected], [email protected], [email protected]
LUISA GARGANO
Affiliation:
Dipartimento di Informatica, University of Salerno, 84084 Fisciano, Italy Email: [email protected]
WALTER QUATTROCIOCCHI
Affiliation:
Department of Mathematics and Computer Science, University of Siena, 53100 Siena, Italy Email: [email protected], [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the following multi-level opinion spreading model on networks. Initially, each node gets a weight, from the set {0,. . .,k – 1}, which measures the individual conviction of a new idea or product. Then, by proceeding in rounds, each node updates its weight according to those of its neighbours. We study k-dynamos that are initial assignments of weights leading each node to get the value k – 1 – e.g. unanimous maximum level of acceptance – within a given number of rounds; the goal is to minimize the sum of the initial weights of the nodes. We determine lower bounds on the sum of the initial weights under the irreversible simple majority rules, where a node increases its weight if and only if the majority of its neighbours have a weight that is higher than its own. We study the relations among 2-dynamos and k-dynamos, with and without a bound on the number of rounds needed to reach the desired all-(k – 1) configuration. Moreover, we provide constructive tight upper bounds for some classes of regular topologies: rings, tori and cliques.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 2: Special Issue: XIV ICTCS , February 2017 , pp. 234 - 256
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

An extended abstract of this paper was presented at 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG'12) (Brunetti et al. 2012).

References

Alba, J., Hutchinson, J. W. and Lynch, J. (1991). Memory and decision making. In: Robertson, T. S. and Kassarjian, H. (eds.) Handbook of Consumer Behaviour, American Marketing Association, Birmingham, Alabama.Google Scholar
Bermond, J. C., Bond, J., Peleg, D. and Perennes, S. (1996). Tight bounds on the size of 2-monopolies. In: Proc. 3rd Colloc. on Structural Information and Communication Complexity (SIROCCO) 170–179.Google Scholar
Bermond, J. C., Bond, J., Peleg, D. and Perennes, S. (2003). The power of small coalitions in graphs. Discrete Applied Mathematics 127 (3) 399–414.Google Scholar
Bermond, J. C., Gargano, L., Rescigno, A. A. and Vaccaro, U. (1998). Fast gossiping by short messages. SIAM Journal on Computing 27 (4) 917–941.Google Scholar
Brunetti, S., Cordasco, G., Gargano, L., Lodi, E. and Quattrociocchi, W. (2012). Minimum weight dynamo and fast opinion spreading. In: Proceedings of 38th International Workshop in Graph Theoretic Concept in Computer Science (WG2012).Google Scholar
Brunetti, S., Lodi, E. and Quattrociocchi, W. (2011). Dynamic monopolies in coloured tori. In: IPDPS Workshops 626–631.Google Scholar
Centola, D. (2010). The spread of behaviour in an online social network experiment. Science 329 (5996) 1194–1197.CrossRefGoogle Scholar
Chen, N. (September 2009). On the approximability of influence in social networks. SIAM Journal of Discrete Mathematics 23 (3) 1400–1415.CrossRefGoogle Scholar
Cicalese, F., Cordasco, G., Gargano, L., Milanič, M. and Vaccaro, U. (2014). Latency-bounded target set selection in social networks. Theoretical Computer Science - Elsevier (TCS) 535 1–15. ISSN: .Google Scholar
Domingos, P. and Richardson, M. (2001). Mining the network value of customers. In: KDD'01: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 57–66, New York, NY, USA.Google Scholar
Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press.Google Scholar
Flocchini, P., Královič, R. Ružička, P. Roncato, A. and Santoro, N. (2003). On time versus size for monotone dynamic monopolies in regular topologies. Journal of Discrete Algorithms 1 (2) 129–150.Google Scholar
Flocchini, P., Lodi, E., Luccio, F., Pagli, L. and Santoro, N. (2004). Dynamic monopolies in Tori. Discrete Applied Mathematics 137 (2) 197–212.Google Scholar
Granovetter, M. (1985). Economic action and social structure: The problem of embeddedness. American Journal of Sociology 91 (3) 481–510.Google Scholar
Kempe, D., Kleinberg, J. and Tardos, E. (2003). Maximizing the spread of influence through a social network. In: KDD'03: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 137–146, New York, NY, USA, ACM.Google Scholar
Kulich, T. (2011). Dynamic monopolies with randomized starting configuration. Theoretical Computer Science 412 (45) 6371–6381.Google Scholar
Linial, N., Peleg, D., Rabinovich, Y. and Saks, M. (1993). Sphere packing and local majorities in graphs. In: ISTCS IEEE Computer Soc. Press 141–149.Google Scholar
Mishra, S. and Rao, S. B. (2003). Minimum monopoly in regular and tree graphs. Electronic Notes in Discrete Mathematics 15 (0) 126.Google Scholar
Nayak, A., Pagli, L. and Santoro, N. (1992). Efficient construction of catastrophic patterns for vlsi reconfigurable arrays with bidirectional links. In: ICCI 79–83.Google Scholar
Peleg, D. (1998). Size bounds for dynamic monopolies. Discrete Applied Mathematics 86 (2–3) 263–273.CrossRefGoogle Scholar
Peleg, D. (2002). Local majorities, coalitions and monopolies in graphs: A review. Theoretical Computer Science 282 (2) 231–257.Google Scholar
Ugander, J., Lars, B., Cameron, M. and Kleinberg, J. (2012). Structural diversity in social contagion. In: Proceedings of the National Academy of Sciences.Google Scholar
Valente, T. W. and Cresskill, N. J. (eds.) (1995). Network Models of the Diffusion of Innovations, Hampton Press.Google Scholar