# The Impact of Community Structure on the Convergence Time of Opinion Dynamics

Authors: An Lu; Chunhua Sun; Yezheng Liu
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

We analyze the convergence time of opinion dynamics in a social network with community structure. Using matrix analysis, we prove that the convergence time is determined by the second largest eigenvalue modulus. This modulus is close to 1 if the social influence matrix is nearly uncoupled. Furthermore, we discuss and analyze the factors of community structure affecting the convergence time.


---

## Body

## 1. Introduction

Community structure is ubiquitous in reality. It means that many social networks can be divided into some groups such that the connection within each group is dense, while connection between groups is very sparse. Community structure is always relevant to many social and biological phenomena. Previous works have shown that community structure affects the evolution of macroscopic phenomena taking place on a network, such as synchronization [1, 2], the spread of epidemics [3, 4], rumors [5], and opinion dynamics [6–8].In opinion dynamics, various versions of the opinion models have been proposed. First types are discrete opinion models, among which are the Sznajd model [9], the voter model [10, 11], the majority rule model [12], and the social impact model [13]. Other models are continuous, using concepts and methods based on ideas from statistical physics or control theory. The most famous are bounded confidence model [14, 15] and an earlier model, Degroot model [16], including some agent-based models such as [17].There are two interesting questions in opinion dynamics. First, under what conditions will the opinions’ updating processes converge to a well-defined limit? The second question is about the convergence time or convergence rate problem; that is, how quickly the consensus is reached if opinions can converge ultimately. Previous works have shown that the convergence time is determined by the topology of social network and the updating rule of individuals’ opinion. For example, in bounded confidence model [15], the convergence time is determined by bounded confidence parameter, which is expressed by a real number ε, such that an agent, with opinion x, only interacts with its peers whose opinion lies in the range of [x-ε,x+ε]. In another bounded confidence model, Deffuant model [14], the convergence time is only determined by convergence parameter μ. In [18], the authors studied the effects of adding shortcuts connecting randomly chosen pairs of sites in a regular lattice on the consensus time, using a local majority updating rule. They showed that the consensus time dropped sensitively with the addition of a small number of shortcuts. In [19], the author introduced a two-state opinion dynamics model where agents evolve by majority rule, finding that consensus is reached in a time that scales to log⁡N, where N is the number of agents. On finite-dimensional lattices, where a group is a contiguous cluster, the consensus time fluctuates strongly between realizations and grows as a dimension-dependent power of N. The upper critical dimension appears to be larger than 4. In [20] the authors found that, for the voter model, if the network is with an arbitrary but uncorrelated degree distribution, the convergence time TN scales as Nμ12/μ2, where µk is the kth moment of the degree distribution and N is the size of the network. In [21], the authors found in a coevolving network that if the number of committed agents added exceeds a critical value, the consensus time growth becomes logarithmic in network size N. Slight changes in the interaction rule can produce strikingly different results of consensus time.Although it is shown that interaction rules or network topologies have an important impact on the evolution of group opinions, the continuous opinion dynamics issue with community structure is still not well understood. Unlike all the research above, here we mainly discuss the impact of a community structure on convergence time, which applies to situations of how we control the opinion evolution in a social network with community structure. First, through matrix analysis method, we prove that the convergence time is determined by the second largest eigenvalue modulus of social influence matrix. Furthermore, we prove that this modulus is close to 1 if the social influence matrix is nearly uncoupled. Second, in our model the influence of interpersonal is random, which is closer to reality. We propose the concept, distribution of interpersonal influence, which can better describe the interaction situations. We examine this issue from three points of view: the number of nodes connected (including the number of nodes connected between subgroups, the number of nodes connected within subgroups, and the connection density between subgroups), the size of subgroups, and influence distribution. We find that the number of connections between subgroups and the number of subgroups within the subgroups exert a strong influence on the convergence time. In addition, the impact of distribution of influence on the convergence time shows the following fact: the convergence time of the group opinions in an autocratic society is longer than that in a democratic society in average, but various connection patterns may bring much more uncertainty.The remaining of this paper is organized as follows: in Section2, we discuss the proposed model in detail. Then in Section 3 we analyze the impact of community structure on the consensus time. Section 4 concludes this paper.


## 2. Continuous Opinion Dynamics Model

### 2.1. Notations, Assumptions, and the Opinion Dynamic Model

This section introduces the notations and the assumptions and defines the consensus time of continuous opinion dynamics.Mathematically, a social network with community structure can be characterized by a big graph in which the nodes represent people, and the edges evaluate their relation strength.We consider a set ofn individuals in a social network. V={1,2,…,n}. A relation E⊆V×V models the interactions between individuals. We assume the relationship is mutual ((i,j)∈E if and only if (j,i)∈E). V is the set of vertices and E is a set of edges of undirected graph G=(V,E), describing the social network of individuals. Each individual has an opinion modeled by a real number xi(t)∈R. Initially, individual i has an opinion xi(0) independent from others. Then, at every time step, the individuals update their opinion by taking a weighted average of their own opinion and opinions of others(1)xit+1=∑j=1naijtxjtwith the coefficients aij(t) satisfying (2)∀i,j∈V,aijt≠0⟺j∈i∪Nit,∑j=1naijt=1,where the coefficient aii denotes the force of self-confidence of individual i and aij denotes to what extent individual i is affected by individual j. Ni(t) denotes the neighborhood of individual i at time t step.LetX(t)=(x1(t),x2(t),…,xn(t))T, A(t)=(aij(t))n×n; thus, the group opinion dynamics can be written as follows: (3)Xt+1=AtXt,where A is a row stochastic and nonnegative matrix. In this following, we call itsocial influence matrix whose entry aij represents the influence strength from individuals j to i.In this paper, we assume that (1) G is static and strongly connected; (2) the relationship and interaction between individuals are mutual; (3) every individual has a little self-confidence. Under these conditions, it is easy to find that A is constant and row stochastic matrix. The diagonal entries in A are all positive, and zero-entries in A are symmetric. Using nonnegative matrix theories, we can get some properties as follows.Proposition 1.
Consensus will be reached ultimately.Proof.
Under assumption (1), it can easily be seen that A is an irreducible, row stochastic and nonnegative matrix. The summation of each row is equal to 1. Thus, the spectral radius of A denoted by ρ(A)=1. α1=(1,1,…,1)T is an eigenvector of λ=1. Since all the diagonal entries are positive, using Perron-Frobenius theory, we can get A is primitive. The algebraic multiplicity of λ=1 is equal to 1. So the spectrum of A can be denoted by(4)specA=λi∣λn≤λn-1≤⋯≤λ2<λ1=1.
For any initial opinion vectorX(0)=(x1(0),x2(0),…,xn(0))T, it can be written as a linear combination as follows:(5)X0=∑i=1nkiαi,where αi is eigenvector corresponding to the eigenvalue λi of A. Thus, for all t>0, αit is an eigenvector corresponding to the eigenvalue λit of At. Since λn≤λn-1≤⋯≤λ2<λ1=1, it follows that(6)limt→∞⁡Xt=limt→∞⁡At·X0=limt→∞⁡At∑i=1nkiαi=limt→∞⁡∑i=1nkiαi·λit=limt→∞⁡k1α1+o1=k1,k1,…,k1T.So the opinions converge to a constant vector, whose components are all equal. That means the consensus can be reached, and the convergence time is consensus time.
Remark. Assumption (2) is not necessary condition but sufficient for convergence of opinions. For example, if A=00.50.5100010, we can get limt→∞⁡At=0.40.40.20.40.40.20.40.40.2, so opinions converge to a fixed vector, but the diagonal of A is not positive.Proposition 2.
The convergence time is determined by the second largest eigenvalue modulusλ2.Proof.
First we introduce the definition of convergence time:(7)t∗=inf⁡t0∣∀t>t0,Xt-X≤δ,where δ can be arbitrarily small, X(t) represents a series of vector, and X is the limit of X(t).
· represents a vector norm (1-norm, 2-norm, or ∞-norm). If X(t)-X<δ, it follows that (8)k2α2·λ2t+oλ2t≤δ;when δ is small enough, o(λ2t) can be omitted. So (7) can be rewritten as k2α2·λ2t≤δ.
Thus, we can get(9)t≥-cln⁡δln⁡1/λ2=-cln⁡δ-ln⁡λ2satisfying (7). So the convergence time t∗=-cln⁡δ/-ln⁡λ2, where c is a constant determined by the initial opinion vector and eigenvector of weighted matrix A.
From the analysis above, it is obvious that the largerλ2 is, the longer the consensus time is and vice versa. For simplicity, we analyze the convergence time only by the second largest eigenvalue modulus λ2 or -ln⁡λ2.Proposition 3.
For a nonnegative row stochastic partitioned matrixA=BDECn×n, where B=(bij)n1×n1, C=(cij)n2×n2, n=n1+n2. Let σ(A) be the summation of entries in D and E; then for any ε>0, ∃δ>0, if σ(A)<δ, satisfying λ2-1<ε.Proof.
First, we prove that if all the entries in a matrix change a little, the eigenvalues of the new matrix will also change. DenoteB by(10)b11b12⋯b1,n1b21b22⋯b2,n1⋮⋮⋮⋮bn1,1bn1,2⋯bn1,n1;step 1 B is transformed into(11)B1=b11+Δ1b12⋯b1,n1b21b22⋯b2,n1⋮⋮⋮⋮bn1,1bn1,2⋯bn1,n1.Thanks to the continuity of eigenvalues, we can get that, for any ε>0, there exists δ(1)>0, if Δ(1)<δ(1), satisfying λ(B(1))-λ(B)<ε. For step 2 when B(1) is transformed into(12)B2=b11+Δ1b12+Δ2⋯b1,n1b21b22⋯b2,n1⋮⋮⋮⋮bn1,1bn1,2⋯bn1,n1,we can get that, ∀ε>0, ∃δ(2)>0, if Δ(2)<δ(2), λ(B(2))-λ(B(1))<ε. Repeat this process, at the last step, ∃δ(n12)>0, if Δ(n12)<δ(n12), λ(B(n12))-λ(B(n12-1))<ε, so for any ε>0, there exists δ′=min(δ1,δ2,…,δ(n12)), if Δ(1),Δ(2),…,Δn12<δ′, satisfying λ(B(n12))-λ(B)<n12ε.
That is to say, if the matrix perturbation is small enough, the eigenvalues will vary little accordingly. Secondly, letA′=B′00C′n×n. So it is reducible, and naturally the spectral of A′  spec(A′)=spec(B′)∪spec(C′). If σ(A) is small enough, then all the entries in D and E are also small. When σ(A) trends toward 0, the entries in B and C must change a little accordingly to keep A as a row stochastic matrix. Without loss of generality, we can assume only one element d11>0 in matrix D (or c11 in C). For these reasons, we can obtain that, for any ε>0, there exists δ, if d11<δ, λ(A)-λ(A′)<ε, since d11<σ(A); if σ(A)<δ, then, d11<δ, λ(A)-λ(A′)<ε or specially λ2-1<ε. That is to say, if σ(A)→0, then the second largest eigenvalue modulus is nearly 1. The inverse of Proposition 3 has been proved by [22]. If second largest eigenvalue is sufficiently close to 1, then A is nearly uncoupled.
A social network with community structure means partitioned matrixA with σ(A) is very small. According to the above analysis, if individuals in different subgroups of a society rarely interact with each other, then λ2 will be very close to 1. As a result, it is hard to reach a consensus.


## 2.1. Notations, Assumptions, and the Opinion Dynamic Model

This section introduces the notations and the assumptions and defines the consensus time of continuous opinion dynamics.Mathematically, a social network with community structure can be characterized by a big graph in which the nodes represent people, and the edges evaluate their relation strength.We consider a set ofn individuals in a social network. V={1,2,…,n}. A relation E⊆V×V models the interactions between individuals. We assume the relationship is mutual ((i,j)∈E if and only if (j,i)∈E). V is the set of vertices and E is a set of edges of undirected graph G=(V,E), describing the social network of individuals. Each individual has an opinion modeled by a real number xi(t)∈R. Initially, individual i has an opinion xi(0) independent from others. Then, at every time step, the individuals update their opinion by taking a weighted average of their own opinion and opinions of others(1)xit+1=∑j=1naijtxjtwith the coefficients aij(t) satisfying (2)∀i,j∈V,aijt≠0⟺j∈i∪Nit,∑j=1naijt=1,where the coefficient aii denotes the force of self-confidence of individual i and aij denotes to what extent individual i is affected by individual j. Ni(t) denotes the neighborhood of individual i at time t step.LetX(t)=(x1(t),x2(t),…,xn(t))T, A(t)=(aij(t))n×n; thus, the group opinion dynamics can be written as follows: (3)Xt+1=AtXt,where A is a row stochastic and nonnegative matrix. In this following, we call itsocial influence matrix whose entry aij represents the influence strength from individuals j to i.In this paper, we assume that (1) G is static and strongly connected; (2) the relationship and interaction between individuals are mutual; (3) every individual has a little self-confidence. Under these conditions, it is easy to find that A is constant and row stochastic matrix. The diagonal entries in A are all positive, and zero-entries in A are symmetric. Using nonnegative matrix theories, we can get some properties as follows.Proposition 1.
Consensus will be reached ultimately.Proof.
Under assumption (1), it can easily be seen that A is an irreducible, row stochastic and nonnegative matrix. The summation of each row is equal to 1. Thus, the spectral radius of A denoted by ρ(A)=1. α1=(1,1,…,1)T is an eigenvector of λ=1. Since all the diagonal entries are positive, using Perron-Frobenius theory, we can get A is primitive. The algebraic multiplicity of λ=1 is equal to 1. So the spectrum of A can be denoted by(4)specA=λi∣λn≤λn-1≤⋯≤λ2<λ1=1.
For any initial opinion vectorX(0)=(x1(0),x2(0),…,xn(0))T, it can be written as a linear combination as follows:(5)X0=∑i=1nkiαi,where αi is eigenvector corresponding to the eigenvalue λi of A. Thus, for all t>0, αit is an eigenvector corresponding to the eigenvalue λit of At. Since λn≤λn-1≤⋯≤λ2<λ1=1, it follows that(6)limt→∞⁡Xt=limt→∞⁡At·X0=limt→∞⁡At∑i=1nkiαi=limt→∞⁡∑i=1nkiαi·λit=limt→∞⁡k1α1+o1=k1,k1,…,k1T.So the opinions converge to a constant vector, whose components are all equal. That means the consensus can be reached, and the convergence time is consensus time.
Remark. Assumption (2) is not necessary condition but sufficient for convergence of opinions. For example, if A=00.50.5100010, we can get limt→∞⁡At=0.40.40.20.40.40.20.40.40.2, so opinions converge to a fixed vector, but the diagonal of A is not positive.Proposition 2.
The convergence time is determined by the second largest eigenvalue modulusλ2.Proof.
First we introduce the definition of convergence time:(7)t∗=inf⁡t0∣∀t>t0,Xt-X≤δ,where δ can be arbitrarily small, X(t) represents a series of vector, and X is the limit of X(t).
· represents a vector norm (1-norm, 2-norm, or ∞-norm). If X(t)-X<δ, it follows that (8)k2α2·λ2t+oλ2t≤δ;when δ is small enough, o(λ2t) can be omitted. So (7) can be rewritten as k2α2·λ2t≤δ.
Thus, we can get(9)t≥-cln⁡δln⁡1/λ2=-cln⁡δ-ln⁡λ2satisfying (7). So the convergence time t∗=-cln⁡δ/-ln⁡λ2, where c is a constant determined by the initial opinion vector and eigenvector of weighted matrix A.
From the analysis above, it is obvious that the largerλ2 is, the longer the consensus time is and vice versa. For simplicity, we analyze the convergence time only by the second largest eigenvalue modulus λ2 or -ln⁡λ2.Proposition 3.
For a nonnegative row stochastic partitioned matrixA=BDECn×n, where B=(bij)n1×n1, C=(cij)n2×n2, n=n1+n2. Let σ(A) be the summation of entries in D and E; then for any ε>0, ∃δ>0, if σ(A)<δ, satisfying λ2-1<ε.Proof.
First, we prove that if all the entries in a matrix change a little, the eigenvalues of the new matrix will also change. DenoteB by(10)b11b12⋯b1,n1b21b22⋯b2,n1⋮⋮⋮⋮bn1,1bn1,2⋯bn1,n1;step 1 B is transformed into(11)B1=b11+Δ1b12⋯b1,n1b21b22⋯b2,n1⋮⋮⋮⋮bn1,1bn1,2⋯bn1,n1.Thanks to the continuity of eigenvalues, we can get that, for any ε>0, there exists δ(1)>0, if Δ(1)<δ(1), satisfying λ(B(1))-λ(B)<ε. For step 2 when B(1) is transformed into(12)B2=b11+Δ1b12+Δ2⋯b1,n1b21b22⋯b2,n1⋮⋮⋮⋮bn1,1bn1,2⋯bn1,n1,we can get that, ∀ε>0, ∃δ(2)>0, if Δ(2)<δ(2), λ(B(2))-λ(B(1))<ε. Repeat this process, at the last step, ∃δ(n12)>0, if Δ(n12)<δ(n12), λ(B(n12))-λ(B(n12-1))<ε, so for any ε>0, there exists δ′=min(δ1,δ2,…,δ(n12)), if Δ(1),Δ(2),…,Δn12<δ′, satisfying λ(B(n12))-λ(B)<n12ε.
That is to say, if the matrix perturbation is small enough, the eigenvalues will vary little accordingly. Secondly, letA′=B′00C′n×n. So it is reducible, and naturally the spectral of A′  spec(A′)=spec(B′)∪spec(C′). If σ(A) is small enough, then all the entries in D and E are also small. When σ(A) trends toward 0, the entries in B and C must change a little accordingly to keep A as a row stochastic matrix. Without loss of generality, we can assume only one element d11>0 in matrix D (or c11 in C). For these reasons, we can obtain that, for any ε>0, there exists δ, if d11<δ, λ(A)-λ(A′)<ε, since d11<σ(A); if σ(A)<δ, then, d11<δ, λ(A)-λ(A′)<ε or specially λ2-1<ε. That is to say, if σ(A)→0, then the second largest eigenvalue modulus is nearly 1. The inverse of Proposition 3 has been proved by [22]. If second largest eigenvalue is sufficiently close to 1, then A is nearly uncoupled.
A social network with community structure means partitioned matrixA with σ(A) is very small. According to the above analysis, if individuals in different subgroups of a society rarely interact with each other, then λ2 will be very close to 1. As a result, it is hard to reach a consensus.


## 3. The Impact of Community Structure on Convergence Time

Although we have some analytical results of the second largest eigenvalue modulus of the social influence matrix with community structure, the exact results depend on entries of this matrix. Different network structures or different influence distributions will affect the second largest eigenvalue modulus, which in turn affects the convergence time of the group opinion. Therefore, the analysis of the impact of community structure on the convergence of time includes the following three aspects: the number of connection nodes, the size of subgroups, and the distribution of interpersonal influence.


### 3.1. The Number of Connection Nodes

First of all, using the famous WS model [23], we build a social network containing two subgroups, respectively. Each social network is a small world. To ensure the whole network is linked, the nodes between subgroups are connected sparsely and randomly. And then we investigate whether the increasing of connection can influence the convergence time.Figure1 shows that the convergence rate of opinion evolution is highly dependent on the connection pattern between subgroups. If the number of connections or connection densities between subgroups increases, the convergence rate of the group opinions is faster. At the beginning, when there is only one connection between subgroups, there is almost no connection between two subgroups, and the convergence rate is almost zero. This is the result of the aforementioned Proposition 3, and in this case, the social influence matrix associated the social network is nearly uncoupled. So consensus is hardly reached. However, when the number of connections (or densities) between the groups increases, for example, when the number of nodes increases to 10 pairs, the second largest eigenvalue modulus λ2 will reduce from 0.9972 to 0.9881. When the number of connections nodes goes up to 100, λ2 will drop to 0.9081 accordingly.Figure 1
The relationship between the number of edges added between two subgroups and the convergence time.However, the convergence rate in Figure2 declines with the rise of the number of internal connections in one subgroup. But the rate of weakening is much slower than that in Figure 1. In Figure 2, with the ascent in the internal connection of the subgroup (from the beginning of the connection density 0.1 is 0.9512; the second largest eigenvalue modulus decreases slightly to 0.9561 when the number of connected nodes ascends to 100 pairs).Figure 2
The relationship between the number of edges added in one subgroup and the convergence time.In Figure3, we explore the impact of two subgroups interaction frequency on the consensus time. Frequency of interaction in the first subgroup is denoted by p1, and the second is p2. The interaction frequency between subgroups is denoted by p3, which is the proportion of positive entries to all the entries in D and E (or the connection density between different subgroups).Figure 3
Example of the frequency of interaction between different subgroups impact on the second largest eigenvalue modulus, withn1=100, n2=50, p1=0.2, and p2=0.4 (repeatedly calculating 30 times).In Figure3, it is easily to be observed that if the parameter p3 goes up, the second largest eigenvalue modulus will fall off. Thus, the consensus time will be shorter with the increasing frequency of interaction between subgroups.


### 3.2. The Size of Subgroups

In this section, we examine the impact of the size of subgroups on the convergence time. For a fixed size, for example, 150, of the social network, Figure4 shows that λ2 will be the largest when n1 is close to n2. More precisely, if p1=p2, when n1=n2=75, λ2 will be the largest. That is to say, if a social network has a small subgroup and a large subgroup simultaneously, it will always be easy to reach a consensus. On the contrary, if the sizes of two subgroups are about the same, it is difficult to reach a consensus.Figure 4
The relationship between the size of subgroups and the second largest eigenvalue modulus.x-axis is the size of one subgroup and y-axis is the second largest eigenvalue modulus. Here we assume the size of G is 150, p3=0.02, in (a), p1=p2=0.2; in (b), p1=0.2, p2=0.4; in (c), p1=0.4, p2=0.2.
(a)
(b)
(c)Simulation results show that the second largest eigenvalue modulus is negatively correlated to the size of the corresponding graph ofA, as well as the density (or average degrees) of the underling graph. For convenience, they are roughly denoted by (13)λ2=fn,p,∂f∂n<0,∂f∂p<0.If the interaction between subgroups is very small,A is nearly uncoupled; using Proposition 3 we can get(14)specA≈specB∪specC;thus,(15)λ2A≈max⁡λ2B,λ2C,i.e.,λ2A≈max⁡fn1,p,fn-n1,p=fmin⁡n1,n-n1,p.So for fixedn, if n1=n/2, min(n1,n-n1) can be the largest, accordingly λ2 is the largest.


### 3.3. The Distribution of Interpersonal Influence

Finally, we study three different distributions of influence strength of individuals. In Figure5 Case 1, power law distribution represents an autocratic society, where minority-influential individuals or opinion leaders exist, and the latter two both represent a democratic society. In Case 2, the influence of individuals follows normal distribution. In Case 3, all individuals are affected by their neighbors with the same influence. Repeatedly calculating 1000 times, we can get the distribution of convergence rate as illustrated in Figure 5. It can be seen that, in an autocratic society (Case 1), the convergence of rate is slow with high probability, but sometimes is very fast. This is due to the asymmetry and heterogeneity of the power law distribution. If a few influential nodes belonging to different subgroups connect with each other, it will accelerate the convergence of groups opinions. On the contrary, if influential nodes form links only by inner-group, it will slightly slow down the convergence of group opinions. Thus, to some extent, the convergence time or convergence rate of group opinions is uncertain in this case. In a democratic society (Case 2 and Case 3), the convergence time follows a narrow-range distribution. In general, the average convergence rate is faster than that of Case 1. In Case 3, the influence matrix can be expressed as A=(D+I)-1MA, where MA is the adjacency matrix of the graph. In this case, all the eigenvalues are real, and the second largest eigenvalue is determined by the maximum degree of the graph.Figure 5
The distribution of convergence rate of group opinion is determined by the distribution of influence.x-axis is the convergence rate -log⁡(λ2) and y-axis is the frequency (total frequency is 1000). (a) represents autocratic society; (b) and (c) represent democratic society.
(a)
(b)
(c)


## 3.1. The Number of Connection Nodes

First of all, using the famous WS model [23], we build a social network containing two subgroups, respectively. Each social network is a small world. To ensure the whole network is linked, the nodes between subgroups are connected sparsely and randomly. And then we investigate whether the increasing of connection can influence the convergence time.Figure1 shows that the convergence rate of opinion evolution is highly dependent on the connection pattern between subgroups. If the number of connections or connection densities between subgroups increases, the convergence rate of the group opinions is faster. At the beginning, when there is only one connection between subgroups, there is almost no connection between two subgroups, and the convergence rate is almost zero. This is the result of the aforementioned Proposition 3, and in this case, the social influence matrix associated the social network is nearly uncoupled. So consensus is hardly reached. However, when the number of connections (or densities) between the groups increases, for example, when the number of nodes increases to 10 pairs, the second largest eigenvalue modulus λ2 will reduce from 0.9972 to 0.9881. When the number of connections nodes goes up to 100, λ2 will drop to 0.9081 accordingly.Figure 1
The relationship between the number of edges added between two subgroups and the convergence time.However, the convergence rate in Figure2 declines with the rise of the number of internal connections in one subgroup. But the rate of weakening is much slower than that in Figure 1. In Figure 2, with the ascent in the internal connection of the subgroup (from the beginning of the connection density 0.1 is 0.9512; the second largest eigenvalue modulus decreases slightly to 0.9561 when the number of connected nodes ascends to 100 pairs).Figure 2
The relationship between the number of edges added in one subgroup and the convergence time.In Figure3, we explore the impact of two subgroups interaction frequency on the consensus time. Frequency of interaction in the first subgroup is denoted by p1, and the second is p2. The interaction frequency between subgroups is denoted by p3, which is the proportion of positive entries to all the entries in D and E (or the connection density between different subgroups).Figure 3
Example of the frequency of interaction between different subgroups impact on the second largest eigenvalue modulus, withn1=100, n2=50, p1=0.2, and p2=0.4 (repeatedly calculating 30 times).In Figure3, it is easily to be observed that if the parameter p3 goes up, the second largest eigenvalue modulus will fall off. Thus, the consensus time will be shorter with the increasing frequency of interaction between subgroups.


## 3.2. The Size of Subgroups

In this section, we examine the impact of the size of subgroups on the convergence time. For a fixed size, for example, 150, of the social network, Figure4 shows that λ2 will be the largest when n1 is close to n2. More precisely, if p1=p2, when n1=n2=75, λ2 will be the largest. That is to say, if a social network has a small subgroup and a large subgroup simultaneously, it will always be easy to reach a consensus. On the contrary, if the sizes of two subgroups are about the same, it is difficult to reach a consensus.Figure 4
The relationship between the size of subgroups and the second largest eigenvalue modulus.x-axis is the size of one subgroup and y-axis is the second largest eigenvalue modulus. Here we assume the size of G is 150, p3=0.02, in (a), p1=p2=0.2; in (b), p1=0.2, p2=0.4; in (c), p1=0.4, p2=0.2.
(a)
(b)
(c)Simulation results show that the second largest eigenvalue modulus is negatively correlated to the size of the corresponding graph ofA, as well as the density (or average degrees) of the underling graph. For convenience, they are roughly denoted by (13)λ2=fn,p,∂f∂n<0,∂f∂p<0.If the interaction between subgroups is very small,A is nearly uncoupled; using Proposition 3 we can get(14)specA≈specB∪specC;thus,(15)λ2A≈max⁡λ2B,λ2C,i.e.,λ2A≈max⁡fn1,p,fn-n1,p=fmin⁡n1,n-n1,p.So for fixedn, if n1=n/2, min(n1,n-n1) can be the largest, accordingly λ2 is the largest.


## 3.3. The Distribution of Interpersonal Influence

Finally, we study three different distributions of influence strength of individuals. In Figure5 Case 1, power law distribution represents an autocratic society, where minority-influential individuals or opinion leaders exist, and the latter two both represent a democratic society. In Case 2, the influence of individuals follows normal distribution. In Case 3, all individuals are affected by their neighbors with the same influence. Repeatedly calculating 1000 times, we can get the distribution of convergence rate as illustrated in Figure 5. It can be seen that, in an autocratic society (Case 1), the convergence of rate is slow with high probability, but sometimes is very fast. This is due to the asymmetry and heterogeneity of the power law distribution. If a few influential nodes belonging to different subgroups connect with each other, it will accelerate the convergence of groups opinions. On the contrary, if influential nodes form links only by inner-group, it will slightly slow down the convergence of group opinions. Thus, to some extent, the convergence time or convergence rate of group opinions is uncertain in this case. In a democratic society (Case 2 and Case 3), the convergence time follows a narrow-range distribution. In general, the average convergence rate is faster than that of Case 1. In Case 3, the influence matrix can be expressed as A=(D+I)-1MA, where MA is the adjacency matrix of the graph. In this case, all the eigenvalues are real, and the second largest eigenvalue is determined by the maximum degree of the graph.Figure 5
The distribution of convergence rate of group opinion is determined by the distribution of influence.x-axis is the convergence rate -log⁡(λ2) and y-axis is the frequency (total frequency is 1000). (a) represents autocratic society; (b) and (c) represent democratic society.
(a)
(b)
(c)


## 4. Conclusions

Based on the framework of the Degroot model, this paper studies the impact of the community structure topology on the consensus time by introducing the second largest eigenvalues modulus of social influence matrix. We prove that if the interaction between subgroups is tiny, then the consensus time will be very long. This means that opinions profiles in a social network with community structure are difficult to reach a consensus.In order to study how the community structure impacts on the convergence time (or the convergence rate), using the second largest eigenvalue modulus, we examine this issue from three points of view: the number of nodes connected (including the number of subgroups connected, the number of subgroups within the connection, and the connection density), subgroup size, and influence distribution. We find that increasing the number of connections between subgroups can accelerate the convergence of group opinions, while increasing the number of subgroups within the subgroups slows the convergence rate. The closer the subgroups’ size is, the longer the convergence time of the group opinions is. On the other hand, the smaller the size of the subgroup is, the shorter the convergence time is. Thus, the community structure depends not only on the density of the subgroups but also on the relative size of the subgroups. In addition, the impact of distribution of influence strength on the convergence time shows that the convergence time of group opinions in an autocratic society is longer than that in a democratic society in average, but may involve more uncertainty, which depends on the various connection pattern.The implication of all the above is network intervene [24]. In order to accelerate the consensus, we must strengthen the communication of individuals in different subgroups. On the contrary, to maintain the discrepancy of group opinions, we can strengthen the communication of individuals in the same subgroups. Another effective way to control opinion evolution is to vary the size of subgroups.



---

*Source: 9396824-2017-06-01.xml*