{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:32Z","timestamp":1759637672152},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2017,2]]},"abstract":"<jats:p>We consider the following multi-level opinion spreading model on networks. Initially, each node gets a weight, from the set {0,.\u00a0.\u00a0.,<jats:italic>k<\/jats:italic> \u2013 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 <jats:italic>k<\/jats:italic>-dynamos that are initial assignments of weights leading each node to get the value <jats:italic>k<\/jats:italic> \u2013 1 \u2013 e.g. unanimous maximum level of acceptance \u2013 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 <jats:italic>k<\/jats:italic>-dynamos, with and without a bound on the number of rounds needed to reach the desired all-(<jats:italic>k<\/jats:italic> \u2013 1) configuration. Moreover, we provide constructive tight upper bounds for some classes of regular topologies: rings, tori and cliques.<\/jats:p>","DOI":"10.1017\/s0960129515000080","type":"journal-article","created":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T09:17:29Z","timestamp":1430903849000},"page":"234-256","source":"Crossref","is-referenced-by-count":1,"title":["Multi-level dynamo and opinion spreading"],"prefix":"10.1017","volume":"27","author":[{"given":"SARA","family":"BRUNETTI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GENNARO","family":"CORDASCO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ELENA","family":"LODI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LUISA","family":"GARGANO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WALTER","family":"QUATTROCIOCCHI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"S0960129515000080_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00241-X"},{"key":"S0960129515000080_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00055-X"},{"key":"S0960129515000080_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"key":"S0960129515000080_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00261-0"},{"key":"S0960129515000080_ref10","doi-asserted-by":"crossref","unstructured":"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\u201366, New York, NY, USA.","DOI":"10.1145\/502512.502525"},{"key":"S0960129515000080_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00043-2"},{"key":"S0960129515000080_ref7","doi-asserted-by":"publisher","DOI":"10.1126\/science.1185231"},{"key":"S0960129515000080_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/08073617X"},{"key":"S0960129515000080_ref14","doi-asserted-by":"publisher","DOI":"10.1086\/228311"},{"key":"S0960129515000080_ref17","doi-asserted-by":"crossref","unstructured":"Linial N. , Peleg D. , Rabinovich Y. and Saks M. (1993). Sphere packing and local majorities in graphs. In: ISTCS IEEE Computer Soc. Press 141\u2013149.","DOI":"10.1109\/ISTCS.1993.253475"},{"key":"S0960129515000080_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283619"},{"key":"S0960129515000080_ref22","doi-asserted-by":"crossref","unstructured":"Ugander J. , Lars B. , Cameron M. and Kleinberg J. (2012). Structural diversity in social contagion. In: Proceedings of the National Academy of Sciences.","DOI":"10.1073\/pnas.1116502109"},{"key":"S0960129515000080_ref23","volume-title":"Network Models of the Diffusion of Innovations","author":"Valente","year":"1995"},{"key":"S0960129515000080_ref5","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1007\/978-3-642-34611-8_26"},{"key":"S0960129515000080_ref15","doi-asserted-by":"crossref","unstructured":"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\u2013146, New York, NY, USA, ACM.","DOI":"10.1145\/956750.956769"},{"key":"S0960129515000080_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.027"},{"key":"S0960129515000080_ref2","unstructured":"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\u2013179."},{"key":"S0960129515000080_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.08.004"},{"key":"S0960129515000080_ref1","volume-title":"Handbook of Consumer Behaviour","author":"Alba","year":"1991"},{"key":"S0960129515000080_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00555-4"},{"key":"S0960129515000080_ref19","doi-asserted-by":"crossref","unstructured":"Nayak A. , Pagli L. and Santoro N. (1992). Efficient construction of catastrophic patterns for vlsi reconfigurable arrays with bidirectional links. In: ICCI 79\u201383.","DOI":"10.1109\/ICCI.1992.227700"},{"key":"S0960129515000080_ref6","unstructured":"Brunetti S. , Lodi E. and Quattrociocchi W. (2011). Dynamic monopolies in coloured tori. In: IPDPS Workshops 626\u2013631."},{"key":"S0960129515000080_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00022-4"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129515000080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,18]],"date-time":"2019-04-18T00:08:44Z","timestamp":1555546124000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129515000080\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["S0960129515000080"],"URL":"https:\/\/doi.org\/10.1017\/s0960129515000080","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]}}}