Lecture notes for COMS 6998 - Social Network Economics
Fall 2013, Columbia University
by A. Chaintreau


Part A.3 - Information selection

All the models we consider so far assume that, when presented with various set of evidence, a user weights new information in a linear manner, while taking into account a personal signal that remains private. It is now time to introduce a subtle effect that we generally refer as an information “selection”. This generally accounts for various effects that have been sometimes be defined and considered separately:

Under any of the forms of these effects (except for “passive” homophily) it is not hard to find simple examples where a population fragments into multiple groups that held different opinions, typically distant, and do not interact. Under most extreme forms of selection, one can observe a polarization either temporarily or persistently. This means that the divergence of opinions increases as time goes, a striking contrast with the prediction of a consensus algorithm.

Homophily

B. Golub and M. O. Jackson, “How homophily affects the speed of learning and best-response dynamics,” The Quarterly Journal of Economics, vol. 127, no. 3, pp. 1287–1338, 2012.

Analyzes iterated averaging on a multi-type uniform random graph (where the probability of an undirected edge (u,v) is Pk,l when u is of type k and v of type l). Iterated averaging in this case converges to average of initial estimator weighted by degree, the question is how fast?

The main contributions are:

NB:

Bounded confidence

Motivation and model

One of the simplest form of information selection comes from extending the general weighted averaging models we have encountered to only operate on opinions that are within a given distance to the current one, corresponding to the rules:

The synchronous nodal updates is sometimes referred to as the Hegselmann-Krause dynamics, and the pairwise update Deffuant-Weisbuch named after the papers that first introduced them.

R. Hegselmann and U. Krause, “Opinion dynamics and bounded confidence models, analysis, and simulation,” Journal of Artificial Societies and Social Simulation, vol. 5, no. 3, 2002.

G. Deffuant, D. Neau, F. Amblard, and G. Weisbuch, “Mixing beliefs among interacting agents,” Advs. Complex Syst., vol. 3, no. 1, pp. 87–98, Jan. 2000.

Most of the analyses of these models have primarily been through numerical simulations. A good example is the study of a critical threshold for the size of the confidence interval (related to the original diameter) to obtain a consensus. This result has not be demonstrated rigorously.

S. Fortunato, “On the consensus threshold for the opinion dynamics of Krause–Hegselmann,” International Journal of Modern Physics C, vol. 16, no. 2, pp. 259–270, 2005.

J. Lorenz, “Continuous opinion dynamics under bounded confidence: A survey,” International Journal of Modern Physics C, vol. 18, no. 12, pp. 1819–1838, 2007.

Proof of convergence

Most of the analytical results deal with characterizing the convergent nature of the process. A relatively classical and general result exploits properties of the product of row-stochastic matrices to prove it in quite generality.

J. Lorenz, “A stabilization theorem for dynamics of continuous opinions,” Physica A: Statistical Mechanics and its Applications, vol. 355, no. 1, pp. 217–223, 2005.

This paper proves that a sequence of row stochastic matrices A(x(t),t) defining a sequence as x(t+1)=A(x(t),t)x(t) eventually converges to classes achieving consensus as long as the following conditions are satisfied:

The proof works as follows: Starting from x(0), we can define the sequence A(t), as A(1)=A(x(0),1) and A(t+1)=A(A(t)x(0),t+1), and we denote for any t1<t2, the product matrix A(t1,t2)=t1t<t2A(t).

Related work on convergence

V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis, “On Krause’s multi-agent consensus model with state-dependent connectivity,” IEEE Transactions on Automatic Control, Jul. 2008.

V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis, “Continuous-Time Average-Preserving Opinion Dynamics with Opinion-Dependent Communications,” SIAM J. Control Optim., vol. 48, no. 8, pp. 5214–5240, Jan. 2010.

In the first paper, the same convergence is obtained using a more specific and more compact set of arguments about the evolution of the system. This paper also obtains lower bounds on the distance between various clusters. The paper also analyzes the limit of the system as the number of agents gets larger, and behave collectively as a continuum.

The second paper considers a differential equation equivalent of the Bounded confidence model (with synchronous nodal udpate). Convergence and some stability properties are established.

B. Chazelle, “Natural algorithms and influence systems,” Communications of the ACM, vol. 55, no. 12, Dec. 2012.

B. Chazelle, “The total s-energy of a multiagent system,” SIAM J. Control Optim., vol. 49, no. 4, pp. 1680–1706, 2011.

B. Chazelle, “Natural algorithms,” presented at the SODA ‘09: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.

B. Chazelle, “The Dynamics of Influence Systems,” Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pp. 311–320, 2012.

The first paper is a review of various works by this author that introduces this area. It remains in general very challenging due to the technicality of the contributions.

The second paper is by far the most readable (and actionable). It proves an extremely general results on the evolution of “bidirectional diffusive systems” which can be generally thought as any system that mixes opinion among arbitrarily formed neighborhood.

Proof of polynomial time convergence

A. Bhattacharyya, M. Braverman, B. Chazelle, and H. L. Nguyen, “On the convergence of the Hegselmann-Krause system,” presented at the ITCS ‘13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science, 2013.

This paper provides a simpler proof of the convergence of the “bounded confidence” dynamics, that is also providing a better polynomial bounds.

This implies in particular that the only minimizer of F(t)(x(t),.) is x(t+1)=(A(t))1Bx(t).
Indeed, to prove this, we can cite one of the fundamental results of linear algebra: To minimize a quadratic form of the type

f:y12yTAybty+c,
(where A is positive semi-definite, b is any vector, and c is a constant) it is sufficient to satisfy Ay=b. To see why, write the gradient of the function in each coordinate and observe that the gradient f is equal to Axb. This proves (1) f is convex, by another derivation, (2) canceling its derivative is sufficient to find a minimizer, which is also unique when A is positive definite. In the later case, you also have since A is invertible that y=A1b.

Note that we also have: F(x,x)=2xT(AB)x and F(x,x)=2xT(A+B)x.

We have just proved that G(t+1)(x(t+1),x(t+1))G(t)(x(t+1),x(t+1))=G(t)(x(t),x(t))[F(x(t),x(t))F(x(t+1),x(t+1))] the last equality simply comes from the fact that all other terms in the sum of G are fixed and do not depend on x. Together with the result above it proves that as time grows:

G(0)(x(0),x(0))G(T)(x(T),x(T))0tT4i||xi(t+1)xi(t)||2

Going further:

Biased Assimilation and Polarization

C. G. Lord, L. Ross, and M. R. Lepper, “Biased assimilation and attitude polarization: The effects of prior theories on subsequently considered evidence.,” Journal of Personality and Social Psychology, vol. 37, no. 11, p. 2098, Nov. 1979.

P. Dandekar, A. Goel, and D. T. Lee, “Biased assimilation, homophily, and the dynamics of polarization.,” Proceedings of the National Academy of Sciences, vol. 110, no. 15, pp. 5791–5796, Apr. 2013.

D. M. Fleder, K. Hosanagar, and A. Buja, “Will the Global Village Fracture into Tribes: Recommender Systems and their Effects on Consumers,” SSRN Journal, 2008. (also mentioned as Hosanagar, K., D. Fleder, D. Lee, and A. Buja. 2013. Recommender Systems and their Effects on Consumers: The Fragmentation Debate. Conditionally Accepted at Management Science.)

Networks with conflicting edges

One reason that may explain continued disagreement and fragmentation or polarization is the presence of active antagonistic edges, corresponding to edges with negative weight. The theory of graphs with positive and negative edges as source of conflicts lead to the theory of structural balance:

D. Cartwright and F. Harary, “Structural balance: a generalization of Heider’s theory.,” Psychological Review, vol. 63, no. 5, pp. 277–293, 1956.

According to this theory, networks containing triangles with an odd number of enemies are probably instable.

S. Marvel, S. Strogatz, and J. M. Kleinberg, “Energy landscape of social balance,” Physical review letters, vol. 103, no. 19, p. 198701, 2009.

S. A. Marvel, J. M. Kleinberg, R. Kleinberg, and S. H. Strogatz, “Continuous-time model of structural balance,” Proceedings of the National Academy of Sciences of the United States of America, vol. 108, no. 5, pp. 1771–1776, 2011.

Proposes an evolution of the graph and show that it reaches structural balance at stability. Study various attractors of these dynamics.

One difficulty of understanding opinion on network with conflicting edges is how to set the transitions between enemies. Various dynamics can be defined

C. Altafini, “Dynamics of opinion forming in structurally balanced social networks,” presented at the Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, 2012, pp. 5876–5881.

C. Altafini, “Consensus Problems on Networks With Antagonistic Interactions,” IEEE Transactions on Automatic Control, vol. 58, no. 4, pp. 935–946, Apr. 2013.

Show that for a normalized dynamic the system either converges to a null opinion for every nodes unless the network is strongly balanced into two camps. In the later case the opinion evolution reaches two antagonistic clusters.

G. Shi, M. Johansson, and K. H. Johansson, “How Agreement and Disagreement Evolve over Random Dynamic Networks,” Selected Areas in Communications, IEEE Journal on, vol. 31, no. 6, pp. 1061–1071, 2013.

Characterizes a different evolution based on attraction/repulsion. Show which ones leads to consensus or divergence in a general network?

G. Shi, A. Proutiere, M. Johansson, J. S. Baras, and K. H. Johansson, “The Evolution of Beliefs over Signed Social Networks,” arXiv.org, Jul. 2013.

Look at an alternative “expansive” interaction between enemies that diverges

M. H. Afrasiabi, R. Guérin, and S. S. Venkatesh, “Opinion formation in Ising networks,” Information Theory and Applications Workshop (ITA), 2013, pp. 1–10, 2013.

Selection in discrete space

R. Axelrod, “The Dissemination of Culture: A Model with Local Convergence and Global Polarization,” Journal of Conflict Resolution, vol. 41, no. 2, pp. 203–226, Apr. 1997.

D. Kempe, J. M. Kleinberg, S. Oren, and A. Slivkins, “Selection and influence in cultural dynamics,” presented at the EC ‘13: Proceedings of the fourteenth ACM conference on Electronic commerce, 2013.

This paper proposes a new dynamics to study selection and influence over a discrete set of states. The elementary action of influence is to attract one node to your own state, a process that is only doable under some compatibility. In addition to that effect, the process accounts for the fact that nodes in different states may spend their attention span only over a selected subset of other states.

Recent works on consensus

U. Krause, “Opinion dynamics–local and global,” Proceedings of the International Workshop Future Directions in Difference Equations., Oct. 2011.

C. Budak, D. Agrawal, and A. El Abbadi, “Limiting the spread of misinformation in social networks,” presented at the WWW ‘11: Proceedings of the 20th international conference on World wide web, 2011.

S. Hong and D. Nadler, “Does the early bird move the polls?: the use of the social media tool ‘Twitter’ by U.S. politicians and its impact on public opinion,” presented at the dg.o ‘11: Proceedings of the 12th Annual International Digital Government Research Conference: Digital Government Innovation in Challenging Times, 2011.

C. J. Kuhlman, V. S. A. Kumar, and S. S. Ravi, “Controlling opinion bias in online social networks,” presented at the WebSci ‘12: Proceedings of the 3rd Annual ACM Web Science Conference, 2012.

A. Mirtabatabaei and F. Bullo, “Opinion Dynamics in Heterogeneous Networks: Convergence Conjectures and Theorems,” SIAM J. Control Optim., vol. 50, no. 5, pp. 2763–2785, Jan. 2012.

P. H. C. Guerra, W. Meira Jr, C. Cardie, and R. Kleinberg, “A Measure of Polarization on Social Media Networks Based on Community Boundaries,” presented at the Proceedings of the International Conference Weblogs and Social Media (ICWSM), 2013.

Written with StackEdit.