Social pressure in opinion dynamics.

*(English)*Zbl 1442.91076Motivated by privacy and security concerns in online social networks, the authors studied the role of social pressure in opinion dynamics. These are dynamics, introduced in economics and sociology literature, that model the formation of opinions in a social network. The authors enriched some of the most classical opinion dynamics, by introducing the pressure, increasing with time, to reach an agreement. They also proved that for clique social networks, the dynamics always converges to consensus if the social pressure is high enough. Moreover, they provided bounds on the speed of convergence. They finally characterized the graphs for which consensus is guaranteed, and made some considerations on the computational complexity of checking whether a graph satisfies such a condition.

They introduced several important results in this paper. Some of the results are given below.

Theorem 1. If \(G\) is a clique, \(S=B=\{0,1\}\), and \(\rho^*> M\), then, for every \(\mathbf{x}\), \(\mathbf{E}_x[\tau]\leq \) \(n^3+k^*\), where \(k^*=\min\{k\mid \rho^{(k)}>M\}\).

Theorem 2. A connected graph \(G\) is well-partitioned if and only if \(G\) has a non-singleton locally minimal cut of a graph \(G = (V , E)\).

Moreover, their case study on Brexit was able to attract more value to support their theories. This paper will surely enrich the area opinion dynamics of social networks.

They introduced several important results in this paper. Some of the results are given below.

Theorem 1. If \(G\) is a clique, \(S=B=\{0,1\}\), and \(\rho^*> M\), then, for every \(\mathbf{x}\), \(\mathbf{E}_x[\tau]\leq \) \(n^3+k^*\), where \(k^*=\min\{k\mid \rho^{(k)}>M\}\).

Theorem 2. A connected graph \(G\) is well-partitioned if and only if \(G\) has a non-singleton locally minimal cut of a graph \(G = (V , E)\).

Moreover, their case study on Brexit was able to attract more value to support their theories. This paper will surely enrich the area opinion dynamics of social networks.

Reviewer: Santanu Acharjee (Golaghat)

##### MSC:

91D30 | Social networks; opinion dynamics |

PDF
BibTeX
XML
Cite

\textit{D. Ferraioli} and \textit{C. Ventre}, Theor. Comput. Sci. 795, 345--361 (2019; Zbl 1442.91076)

Full Text:
DOI

##### References:

[1] | Daron, Acemoglu; Ozdaglar, Asuman, Opinion dynamics and learning in social networks, Dyn. Games Appl., 1, 1, 3-49, (2011) · Zbl 1214.91091 |

[2] | Auletta, Vincenzo; Ferraioli, Diodato; Pasquale, Francesco; Persiano, Giuseppe, Metastability of logit dynamics for coordination games, (SODA ’12, (2012)), 1006-1024 · Zbl 1422.91095 |

[3] | Auletta, Vincenzo; Ferraioli, Diodato; Pasquale, Francesco; Penna, Paolo; Persiano, Giuseppe, Logit dynamics with concurrent updates for local interaction games, (ESA ’13, (2013)), 73-84 · Zbl 1395.91073 |

[4] | Auletta, Vincenzo; Ferraioli, Diodato; Pasquale, Francesco; Persiano, Giuseppe, Mixing time and stationary expected social welfare of logit dynamics, Theory Comput. Syst., 53, 1, 3-40, (2013) · Zbl 1291.91026 |

[5] | Auletta, Vincenzo; Caragiannis, Ioannis; Ferraioli, Diodato; Galdi, Clemente; Persiano, Giuseppe, Minority becomes majority in social networks, (WINE ’15, (2015)), 74-88 · Zbl 1406.91317 |

[6] | Auletta, Vincenzo; Caragiannis, Ioannis; Ferraioli, Diodato; Galdi, Clemente; Persiano, Giuseppe, Generalized discrete preference games, (IJCAI ’16, (2016)), 53-59 |

[7] | Auletta, Vincenzo; Ferraioli, Diodato; Greco, Gianluigi, Reasoning about consensus when opinions diffuse through majority dynamics, (IJCAI, (2018)), 49-55 |

[8] | Auletta, Vincenzo; Fanelli, Angelo; Ferraioli, Diodato, Consensus in opinion formation processes in fully evolving environments, (AAAI’19, (2019)) |

[9] | Bhalgat, Anandd; Chakraborty, Tanmoy; Khanna, Sanjeev, Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games, (EC ’10, (2010)), 73-82 |

[10] | Bhawalkar, Kshipra; Gollapudi, Sreenivas; Munagala, Kamesh, Coevolutionary opinion formation games, (STOC ’13, (2013)), 41-50 · Zbl 1293.91114 |

[11] | BilĂ˛, Vittorio; Fanelli, Angelo; Moscardelli, Luca, Opinion formation games with dynamic social influences, (WINE ’16, (2016)), 444-458 · Zbl 1404.91043 |

[12] | Bindel, David; Kleinberg, Jon; Oren, Sigal, How bad is forming your own opinion?, (FOCS ’11, (2011)), 55-66 · Zbl 1292.91148 |

[13] | Blume, Lawrence E., The statistical mechanics of strategic interaction, Games Econ. Behav., 5, 387-424, (1993) · Zbl 0797.90123 |

[14] | Chierichetti, Flavio; Kleinberg, Jon; Oren, Sigal, On discrete preferences and coordination, J. Comput. Syst. Sci., 93, 11-29, (2018) · Zbl 1408.91041 |

[15] | DeGroot, Morris H., Reaching a consensus, J. Am. Stat. Assoc., 69, 118-121, (1974) · Zbl 0282.92011 |

[16] | Ferraioli, Diodato; Ventre, Carmine, Social pressure in opinion games, (Proceedings of the 26th International Joint Conference on Artificial Intelligence, (2017), AAAI Press), 3661-3667 |

[17] | Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine, Decentralized dynamics for finite opinion games, Theor. Comput. Sci., 648, 96-115, (2016) · Zbl 1414.91072 |

[18] | Friedkin, Noah E.; Johnsen, Eugene C., Social influence and opinions, J. Math. Sociol., 15, 3-4, 193-206, (1990) · Zbl 0712.92025 |

[19] | Gharan, Shayan Oveis; Trevisan, Luca, Partitioning into expanders, (SODA ’14, (2014)), 1256-1266 · Zbl 1423.05182 |

[20] | Grandi, Umberto; Lorini, Emiliano; Perrussel, Laurent, Propositional opinion diffusion, (AAMAS ’15, (2015)), 989-997 |

[21] | Karger, David R., Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm, (SODA ’93, (1993)), 21-30 · Zbl 0801.68124 |

[22] | Kolev, Pavel; Mehlhorn, Kurt, A note on spectral clustering, (ESA ’16, (2016)), 57:1-57:14 · Zbl 1397.68144 |

[23] | McFadden, Daniel, Conditional logit analysis of qualitative choice behavior, (Frontiers in Econometrics, (1974)), 105-142, Number 2 |

[24] | Montanari, Andrea; Saberi, Amin, Convergence to equilibrium in local interaction games, (FOCS ’09, (2009)), 303-312 · Zbl 1292.91036 |

[25] | Mossel, Elchanan; Tamuz, Omer, Opinion exchange dynamics, Probab. Surv., 14, 155-204, (2017) · Zbl 1376.91131 |

[26] | Peng, Richard; Sun, He; Zanetti, Luca, Partitioning well-clustered graphs: spectral clustering works!, (COLT ’15, (2015)), 1423-1455 |

[27] | Young, Hobart Peyton, The diffusion of innovations in social networks, (The Economy As an Evolving Complex System III: Current Perspectives and Future Directions, (2006)), 267 |

[28] | Pigozzi, Gabriella, Belief merging and judgment aggregation, (Zalta, Edward N., The Stanford Encyclopedia of Philosophy, (2016), Metaphysics Research Lab, Stanford University), Winter 2016 edition · Zbl 1112.03305 |

[29] | Pryymak, Oleksandr; Rogers, Alex; Jennings, Nicholas R., Efficient opinion sharing in large decentralised teams, (AAMAS ’12, (2012)), 543-550 |

[30] | Rajtmajer, Sarah; Squicciarini, Anna; Griffin, Christopher; Karumanchi, Sushama; Tyagi, Alpana, Constrained social energy minimization for multi-party sharing in online social networks, (AAMAS ’16, (2016)), 680-688 |

[31] | Schwind, Nicolas; Inoue, Katsumi; Bourgne, Gauvain; Konieczny, Sebastien; Marquis, Pierre, Belief revision games, (AAAI’15, (2015)), 1590-1596 |

[32] | Tsang, Alan; Larson, Kate, Opinion dynamics of skeptical agents, (AAMAS ’14, (2014)), 277-284 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.