No CrossRef data available.
Article contents
Multi-level dynamo and opinion spreading†
Published online by Cambridge University Press: 06 May 2015
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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.
Information
- 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
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
You have
Access
- 1
- Cited by