TY - JOUR
T1 - Opinion dynamics in social networks with stubborn agents
T2 - Equilibrium and convergence rate
AU - Ghaderi, Javad
AU - Srikant, R.
N1 - Funding Information:
Propositions 1–3 First, we present an extremal characterization for the largest eigenvalue of a sub-stochastic (and reversible) matrix. Then, we state the proofs of individual propositions. Recall that A and A ̃ have the same largest eigenvalue. A ̃ is reversible with respect to π ̃ = [ w i Z : i ∈ V ∖ S F ] T (as defined in Lemma 3 ), i.e., π ̃ i A ̃ i j = π ̃ j A ̃ j i . Thus, it follows from extremal characterization of eigenvalues ( Bremaud, 2001 ) that 1 − λ A = inf f ≠ 0 〈 ( I − A ̃ ) f , f 〉 π ̃ 〈 f , f 〉 π ̃ , where the infimum is over all functions f : V ∖ S F → R . The above characterization can also be written as 1 − λ A = inf ϕ ≠ 0 〈 ( I − P ) ϕ , ϕ 〉 π 〈 ϕ , ϕ 〉 π , where now the infimum is over functions ϕ : V ˆ → R , such that ϕ ( S F ∪ u ( S P ) ) = 0 , and P is the random walk (15) . Then, 〈 ( I − P ) ϕ , ϕ 〉 π = E ( ϕ , ϕ ) where E ( ϕ , ϕ ) is the Dirichlet form E ( ϕ , ϕ ) = 1 2 ∑ i , j ∈ V ˆ π i P i j ( ϕ ( i ) − ϕ ( j ) ) 2 . In terms of the edge weights of G ˆ , we get E ( ϕ , ϕ ) = 1 2 w ∑ i , j ∈ V ˆ w i j ( ϕ ( i ) − ϕ ( j ) ) 2 , 〈 ϕ , ϕ 〉 π = 1 w ∑ i ∈ V ∖ S F w i ϕ 2 ( i ) , where w ≔ ∑ i ∈ V ˆ w i . For any vertex i ∈ V ∖ S F , consider a path γ i from i to the set S F ∪ u ( S P ) that does not intersect itself, i.e., γ i = { ( i , i 1 ) , ( i 1 , i 2 ) , … , ( i m , j ) } for some j ∈ S F ∪ u ( S P ) . Note that in this definition the edges are oriented meaning that we distinguish between ( x , y ) and ( y , x ) . Then, we can write ϕ ( i ) = ∑ ( x , y ) ∈ γ i ( ϕ ( x ) − ϕ ( y ) ) because ϕ ( y ) = 0 if y ∈ S F ∪ u ( S P ) . Proof of Proposition 1 The result follows from the extremal characterization of 1 − λ A . Note that 〈 ϕ , ϕ 〉 π = 1 w ∑ i ∈ V ∖ S F w i ( ∑ ( x , y ) ∈ γ i ( ϕ ( x ) − ϕ ( y ) ) ) 2 = 1 w ∑ i ∈ V ∖ S F w i ( ∑ ( x , y ) ∈ γ i 1 w x y w x y ( ϕ ( x ) − ϕ ( y ) ) ) 2 ≤ 1 w ∑ i ∈ V ∖ S F w i ( ∑ ( x , y ) ∈ γ i 1 w x y ) ( ∑ ( x , y ) ∈ γ i w x y ( ϕ ( x ) − ϕ ( y ) ) 2 ) = 1 w ∑ i ∈ V ∖ S F w i | γ i | w ( ∑ ( x , y ) ∈ γ i w x y ( ϕ ( x ) − ϕ ( y ) ) 2 ) = 1 w ∑ x , y ∈ V ˆ w x y ( ϕ ( x ) − ϕ ( y ) ) 2 ( ∑ i : γ i ∋ ( x , y ) w i | γ i | w ) ≤ 2 E ( ϕ , ϕ ) ξ . This concludes the proof. The first inequality follows from the Cauchy–Schwarz inequality and the second one from the definition of ξ . Proof of Proposition 2 The proof is again based on the extremal characterization. Note that 〈 ϕ , ϕ 〉 π = 1 w ∑ i ∈ V ∖ S F w i ( ∑ ( x , y ) ∈ γ i ( ϕ ( x ) − ϕ ( y ) ) ) 2 ≤ 1 w ∑ i ∈ V ∖ S F w i | γ i | ∑ ( x , y ) ∈ γ i ( ϕ ( x ) − ϕ ( y ) ) 2 = 1 w ∑ x , y ∈ V ˆ ( ϕ ( x ) − ϕ ( y ) ) 2 ∑ i : γ i ∋ ( x , y ) w i | γ i | = 1 w ∑ x , y ∈ V ˆ w x y ( ϕ ( x ) − ϕ ( y ) ) 2 1 w x y ∑ i : γ i ∋ ( x , y ) w i | γ i | ≤ 2 E ( ϕ , ϕ ) η , which concludes the proof. Again the first inequality follows from the Cauchy–Schwarz inequality and the second one from the definition of η . Proof of Proposition 3 To find an upper bound on 1 − λ A , consider indicator functions of the form 1 U , U ⊆ V ∖ S F , in the extremal characterization of eigenvalues. Then, we have 1 − λ A ≤ E ( 1 U , 1 U ) 〈 1 U , 1 U 〉 π = ∑ i ∈ U , j ∉ U w i j ∑ i ∈ U w i ≕ ψ ( U ; G ˆ ) , and accordingly, 1 − λ A ≤ min U ⊆ V ∖ S F ψ ( U ; G ˆ ) . It is easy to see that the minimizing U is the vertex set of a connected subgraph of G ∖ S F . Javad Ghaderi received his B.Sc. from the University of Tehran, Iran, in 2006, his M.Sc. from the University of Waterloo, Canada, in 2008, and his Ph.D. from the University of Illinois at Urbana–Champaign (UIUC) in 2013, all in Electrical Engineering. He joined Columbia University as an Assistant Professor of Electrical Engineering in 2014, after a one-year Simons Postdoctoral fellowship at the University of Texas at Austin. His research interests include network algorithms, network control and optimization, and network information theory. He is the recipient of the Mac Van Valkenburg Graduate Research Award at UIUC, and Best Student Paper Finalist at the 2013 American Control Conference. He is currently a Guest Editor of Queueing Systems—Special Issue in Cloud Computing. R. Srikant received his B.Tech. from the Indian Institute of Technology, Madras in 1985, his M.S. and Ph.D. from the University of Illinois in 1988 and 1991, respectively, all in Electrical Engineering. He was a Member of Technical Staff at AT&T Bell Laboratories from 1991 to 1995. He is currently with the University of Illinois at Urbana–Champaign, where he is the Fredric G. and Elizabeth H. Nearing Professor in the Department of Electrical and Computer Engineering, and a Research Professor in the Coordinated Science Lab. He was an associate editor of Automatica, the IEEE Transactions on Automatic Control, the IEEE/ACM Transactions on Networking, and the Journal of the ACM. He has also served on the editorial boards of special issues of the IEEE Journal on Selected Areas in Communications and IEEE Transactions on Information Theory. He was the chair of the 2002 IEEE Computer Communications Workshop in Santa Fe, NM and a program co-chair of IEEE INFOCOM, 2007. He is currently the Editor-in-Chief of the IEEE/ACM Transactions on Networking. He was a Distinguished Lecturer for the IEEE Communications Society for 2011–12. His research interests include communication networks, stochastic processes, queueing theory, information theory, and game theory.
Publisher Copyright:
© 2014 Elsevier Ltd. All rights reserved.
PY - 2014/12/1
Y1 - 2014/12/1
N2 - The process by which new ideas, innovations, and behaviors spread through a large social network can be thought of as a networked interaction game: Each agent obtains information from certain number of agents in his friendship neighborhood, and adapts his idea or behavior to increase his benefit. In this paper, we are interested in how opinions, about a certain topic, form in social networks. We model opinions as continuous scalars ranging from 0 to 1 with 1 (0) representing extremely positive (negative) opinion. Each agent has an initial opinion and incurs some cost depending on the opinions of his neighbors, his initial opinion, and his stubbornness about his initial opinion. Agents iteratively update their opinions based on their own initial opinions and observing the opinions of their neighbors. The iterative update of an agent can be viewed as a myopic cost-minimization response (i.e., the so-called best response) to the others' actions. We study whether an equilibrium can emerge as a result of such local interactions and how such equilibrium possibly depends on the network structure, initial opinions of the agents, and the location of stubborn agents and the extent of their stubbornness. We also study the convergence speed to such equilibrium and characterize the convergence time as a function of aforementioned factors. We also discuss the implications of such results in a few well-known graphs such as Erdos-Renyi random graphs and small-world graphs.
AB - The process by which new ideas, innovations, and behaviors spread through a large social network can be thought of as a networked interaction game: Each agent obtains information from certain number of agents in his friendship neighborhood, and adapts his idea or behavior to increase his benefit. In this paper, we are interested in how opinions, about a certain topic, form in social networks. We model opinions as continuous scalars ranging from 0 to 1 with 1 (0) representing extremely positive (negative) opinion. Each agent has an initial opinion and incurs some cost depending on the opinions of his neighbors, his initial opinion, and his stubbornness about his initial opinion. Agents iteratively update their opinions based on their own initial opinions and observing the opinions of their neighbors. The iterative update of an agent can be viewed as a myopic cost-minimization response (i.e., the so-called best response) to the others' actions. We study whether an equilibrium can emerge as a result of such local interactions and how such equilibrium possibly depends on the network structure, initial opinions of the agents, and the location of stubborn agents and the extent of their stubbornness. We also study the convergence speed to such equilibrium and characterize the convergence time as a function of aforementioned factors. We also discuss the implications of such results in a few well-known graphs such as Erdos-Renyi random graphs and small-world graphs.
KW - Eigenvalues
KW - Equilibrium
KW - Markov models
KW - Multi-agent systems
UR - http://www.scopus.com/inward/record.url?scp=84919481091&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84919481091&partnerID=8YFLogxK
U2 - 10.1016/j.automatica.2014.10.034
DO - 10.1016/j.automatica.2014.10.034
M3 - Article
AN - SCOPUS:84919481091
SN - 0005-1098
VL - 50
SP - 3209
EP - 3215
JO - Automatica
JF - Automatica
IS - 12
ER -