{'fraction_non_alphanumeric': 0.04557336060916013, 'fraction_numerical': 0.016320036367769065, 'mean_word_length': 4.187595802381795, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Transient Behavior of Gossip Opinion Dynamics with Community Structure

We study transient behavior of gossip opinion dynamics, in which agents randomly interact pairwise over a graph with community structure. We first study behavior of the model over a weighted graph with two communities. Edges within a community have identical weights different from edge weights between communities. A sharp phase transition is discovered: When edge weights within communities are larger than those between communities and those between regular and stubborn agents, most agents in the same community hold opinions close to the initial average opinion of that community with large probability, at an early stage of the process. However, if the difference between intra- and inter-community weights is small enough, most of the agents instead hold opinions close to everyone's initial average opinion at the early stage. In contrast, when the influence of stubborn agents is large enough, agent opinions settle quickly into their steady states. We then conduct numerical experiments to validate the theoretical results, and demonstrate extensions to multiple communities and stochastic block models, by providing two numerical examples. Different from the traditional asymptotic analysis in most opinion dynamics literature, the paper characterizes the influences of stubborn agents and community structure on the initial phase of the opinion evolution.


Introduction
Opinion dynamics is the study of how personal opinions change through interactions in social networks. Analysis of convergence and stability of opinion dynamics has gained considerable attention in recent decades [1,2], but less research has focused on transient behavior of the opinion formation process. Social networks often have topologies where subgroups of nodes are densely connected internally but loosely connected with others, which is called community structure [3]. Such structure is observed to be able to influence opinion dynamics [4,5]. It is often difficult to determine whether a realistic social network reaches its stationary state or not, and whether its communities evolve homogeneously at the early stage. So it is necessary to investigate how the opinion formation process, especially during its initial phase, corresponds to its community structure. Such results can also provide insights into design of community detection algorithms based on state observations [6,7] and design of model reduction tools for large-scale networks [8,9].

Related Work
Individual opinion can be modeled by a continuous variable taking values in an interval of real numbers, or a discrete variable in a finite set [2,10]. There are at least three types of continuous-opinion models explaining how interpersonal interactions shape opinion profiles of social networks, namely, models of assimilative, homophily, and negative social influences [2,11]. A crucial example of the first class of models is the DeGroot model [12], in which agents update according to the average of their neighbors' opinions. The Friedkin-Johnsen (FJ) model [13,14,15] generalizes the DeGroot model and allows long-term disagreement, rather than consensus, by assuming that agents are consistently affected by their initial opinions. The Hegselmann-Krause (HK) model [16,17] and the Deffuant-Weisbuch (DW) model [18,19] are representatives of the second class of models. In these models, agents stay away from those who hold different beliefs, and hence the agents tend to form clusters in the end. Negative influences presence in the third class of models can increase opinion difference between individuals, and make the group end in polarization [2,20]. Other factors that may influence the opinion formation process have also been investigated, such as individual memory [21] and private opinions [22]. This paper considers transient behavior of a gossip model with stubborn agents. This model, in which agents randomly interact in pairs, is a stochastic counterpart of the DeGroot model. The model captures the random nature of interpersonal influence and exhibits various behavior. Consensus of the gossip model has been studied in [23,24]. The authors in [25] show that the existence of stubborn agents may explain fluctuation of social opinions, and also that, if the network is highly fluid, then the expected steady states of regular (non-stubborn) agents are close. In contrast, it is shown in [26] that polarization can emerge, if the model evolves over a weighted graph with two stubborn agents.
Less research has focused on transient behavior of the opinion formation process, in contrast to asymptotic analysis, although the transient behavior can be important for practical applications in social networks [27,28] and epidemics [29]. When the size of a network is large, it can take a long time for the system to reach steady states [27,30], but the duration of real dynamics such as election and online discussion is often finite. In addition, it is found that system behavior in transient phase, rather than steady states, can be a good predictor for empirical data [31]. The authors in [27] propose a framework to analyze the transient stage of discrete-state Markov chains that model opinion dynamics. The paper [32] studies quasi-stationary distributions of a contact process, and [33] analyzes the transient opinion profiles of a voter model. The authors in [34] provide criteria for detecting transient clusters in a generalized HK model that normally reaches a consensus asymptotically.
The study of community structure can be traced back to [35,36], in which a community is defined as a complete subgraph in a network. Later work [37] defines communities based on internal and external degrees of subgroups. One of the modern definitions for communities is modularity, which characterizes the nonrandomness of a group partition [38]. The stochastic block model (SBM) [39], which generates random graphs with communities, is another popular framework in the literature of community detection. Researchers have studied how community structure of a network influences opinion evolution, based on several models such as the DW model [40,41], the Taylor model (a continuous-time version of the FJ model) [42], and the Sznajd model [43]. The paper [26] studies the DeGroot model with stubborn agents over a weighted graph, and shows that the steady states of agents in the same community concentrate around the state of some stubborn agent.

Contribution
In this paper, we study transient behavior of the gossip model over a graph with community structure. First, we study the model over a weighted graph with two communities. It is assumed that edges within communities have identical weights different from edge weights between communities. The paper reveals a phase transition phenomenon [44,45,46]: When edge weights within communities are larger than those between communities and those between regular and stubborn agents, most agents in the same community have states with small deviation from the initial average opinion of that community with large probability, at the early stage of the process (Theorem 1 and Corollary 1). Under the situation where weights between regular and stubborn agents are still small, if the difference between intra-and inter-community weights is small enough or the inter-community weights are larger than the intra-community ones, most agents in the network have states concentrating around everyone's initial average opinion with small error and large probability at the early stage (Theorem 2 and Corollary 2). In contrast, if weights between regular and stubborn agents is larger than those between regular agents, agent states have a distribution close to their stationary one, right after the beginning of the process (Theorem 3 and Corollary 3). We conduct several numerical experiments, validating the theoretical results and showing that the transition is sharp, and demonstrate extensions to multiple communities and SBMs.
These results indicate that the gossip model has entirely different transient behavior, under different magnitude of interaction strength within communities, between communities, and between regular and stubborn agents. In other words, sharp transitions are found at the initial stage of the gossip model. It is known that the expected stationary states depend on the positions of stubborn agents [25], and the model reaches a consensus if there are no stubborn agents [23,24]. The obtained results indicate that agents may form transient clusters if the influence of stubborn agents is relatively small. These transient clusters may not be the same as the stationary ones, because they only depend on initial regular-agent states and edge weights between agents. This observation means that transient behavior of the model can be entirely different from the asymptotic behavior. In addition, the results demonstrate how transient behavior of the model corresponds to community structure of the network, by showing that the difference between intra-and inter-community weights has to be large enough to ensure the existence of such a correspondence and by showing how the relative size of the weights influences the duration of the transient clusters.
The results can provide insights into predicting and distinguishing transient behavior of an opinion formation process in practice [27,31]. For example, when the size of a network and the difference between intra-and inter-community interaction strength are large, the duration of such transient interval is expected to be large as well. Given an estimate of the runtime for a process, we may determine whether the current clusters are steady or not. The correspondence between community structure and transient behavior can also inspire development of community detection methods based on state observations [6,7]. Suppose that the network is unknown but several snapshots of an opinion dynamic are available. Then it could be possible to recover the community labels of agents by partitioning agent states. Finally, exploiting properties of transient clusters can help improve model reduction tools at the initial phase of dynamics over large-scale networks with community structure [8,9]. If agents in the same community have states close to each other at the early stage of the process, then we may track the opinion formation process with much less parameters than the original system, by replacing topological data with community labels.
In the early work [47], we study behavior of expected agent states under the condition that the influence of stubborn agents is small. In the current paper we directly study behavior of agent states, and conduct more detailed numerical experiments to investigate the transient behavior.

Outline
In Section 2 we introduce the considered model and problem. Section 3 provides theoretical results. Numerical experiments are presented in Section 4. Section 5 concludes the paper. The proofs of the main theorems are given in appendices.
Notation. Denote the n-dimensional Euclidean space by R n , the set of n × m real matrices by R n×m , the set of nonnegative integers by N, and N + = N \ {0}. Denote the natural logarithm by log x, x ∈ R. Let 1 n be the all-one vector with dimension n, e (n) i be the n-dimensional unit vector with i-th entry being one, I n be the n × n identity matrix, and 0 m,n be the m × n all-zero matrix. Denote the Euclidean norm of a vector by · . For a vector x ∈ R n , denote its i-th entry by x i , and for a matrix A ∈ R n×n , denote its (i, j)-th entry by a ij or [A] ij . The cardinality of a set S is denoted by |S|. The function I [property] is the indicator function equal to one if the property in the bracket holds, and equal to zero otherwise. Denote the expectation of a random vector X by E{X}. For two sequences of real numbers, f (n) and g(n) > 0, n ∈ N, we write f (n) = O(g(n)) if |f (n)| ≤ Cg(n) for all n ∈ N and some C > 0, f (n) = o(g(n)) if |f (n)|/g(n) → 0, and f (n) ∼ g(n) if f (n)/g(n) → 1 as n → ∞. Further assuming f (n), n ∈ N, are nonnegative, we say that f (n) = ω(g(n)) if g(n) = o(f (n)), that f (n) = Ω(g(n)) if there is C > 0 such that f (n) ≥ Cg(n) for all n ∈ N, and that f (n) = Θ(g(n)) if both f (n) = O(g(n)) and f (n) = Ω(g(n)) hold. For x, y ∈ R, denote x ∨ y := max{x, y} and x ∧ y := min{x, y}.

Problem Formulation
The gossip model with stubborn agents is a random process evolving over the graph G = (V, E, A), where V is the node set with |V| = n ≥ 2, E is the edge set, and A is the weighted adjacency matrix. The graph G has no self-loops. V contains two types of agents, regular and stubborn, denoted by V r and V s , respectively (V = V r ∪ V s and V r ∩ V s = ∅). The regular agents form several disjoint communities V r1 , . . . , V rK , for some K ∈ N + (hence Regular agent i has state X i (t) ∈ R at time t ∈ N, and stubborn agent j has state z s j . Stacking these states, we denote the state vector of regular agents at time t by X(t) ∈ R |Vr| and the state vector of stubborn agents by z s ∈ R |Vs| .
The random interaction of the gossip model is captured by an interaction probability matrix W = [w ij ] ∈ R n×n satisfying that w ij = w ji = a ij /α, where α = n i=1 n j=i+1 a ij is the sum of all edge weights. Hence 1 T W 1/2 = 1.
At time t, edge {i, j} is selected with probability w ij independently of previous updates, and agents update as follows, where with n r = |V r | and n s = |V s |. In other words, only regular agents in {i, j} update their states. The averaging weight is assumed to be 1/2, but general weights can be considered.
In this paper, we study how community structure and stubborn agents influence the agent states at the early stage of the process. The problem considered is as follows.
Problem. Given the regular agent state vector X(0), the stubborn agent state vector z s , the community structure C, and the weighted adjacency matrix A, characterize transient behavior of X(t). Numerical examples are given in Section 4, which also shows extensions to multiple communities as well as SBMs.

Theoretical Analysis
In this section, we study transient behavior of gossip model (1) over a weighted graph with two communities. The analysis provides crucial insights into understanding transient behavior of the model under general conditions.
We introduce the following assumptions, illustrated in Fig. 1, for the weighted adjacency matrix A of graph G.
ij ∈ (0, 1) with 1 ≤ i ≤ r 0 n and 1 ≤ j ≤ s 0 n, depending on n, such that a i,r0n+j = a r0n+j,i = l We further impose an assumption for the initial vector of gossip model (1) as follows.

Assumption 2
The initial regular agent state vector X(0) and the stubborn agent state vector z s are deterministic, and satisfy that |X i (0)| ≤ c x and |z s j | ≤ c x , for all 1 ≤ i ≤ r 0 n and 1 ≤ j ≤ s 0 n, and some constant c x > 0.
Now we give some remarks on Assumptions 1 and 2 as follows.

Remark 1
The SBM is a well-accepted random graph model with community structure [3,39]. In this model, nodes are assigned with community labels, and an edge is added to the graph with a probability depending on the community labels of that edge's endpoints. The expected structure of the model can be captured by a weighted graph as in Assumption 1 (i). We assume that the graph on regular agents is such a weighted graph, where edges between agents in the same community have the same weight l (r) s and those between communities have weight l (r) d . These weights can be treated as the probabilities that the corresponding edges exist in the SBM, and also as the interaction strength between agents in the gossip model. Note that we introduce this simplified assumption to highlight the phase transition phenomenon occurred in the transient phase of the dynamics, and proofs of the results under this assumption are still nontrivial. Due to page limit, we do not carry out more careful and lengthy analysis for the SBM case, but in Section 4.3 we will demonstrate behavior of the gossip model over an SBM via simulation.
Parameter l (s) given in Assumption 1 (iii) is the sum of edge weights between one regular agent and all stubborn agents, and thus represents the total influence of stubborn agents on this regular agent. We assume that this sum is the same for all regular agents. This assumption is introduced for analysis simplicity, but can be extended if the upper and lower bounds of the weight sums are available. In Assumption 2, it is assumed that the initial values of all agents are bounded, and thus the process is bounded as well.
From the definitions of Q(t) and R(t) in (1), it follows that where Before presenting main theorems, we provide several properties of the gossip model. The first lemma concerns the explicit expression of the weight sum of the graph G.
Lemma 1 Under Assumption 1, the weight sum α = r 0 n[(l (r) PROOF. The conclusion follows directly from the definition of α and Assumption 1. 2 The next lemma gives the expression of E{X(t)}, and shows how E{X(t)} evolves by decomposing it into three parts, which correspond to the eigenspaces ofQ.
Lemma 2 Suppose that Assumption 1 holds. Then the expectation of X(t) satisfies that, for all t ∈ N, PROOF. From the discussion after (3), it follows that We can obtain the conclusion by noticing In what follows, we introduce some technical assumptions for main theorems.
Assumption 3 Assume the following conditions hold.  (the influence difference of a stubborn agent on the two communities) are of the same order of l (s) . Otherwise, the influence of stubborn agents may not be homogeneous, which could be hard to analyze. Assumption 3 (iii) indicates that the number of stubborn agents is smaller than that of regular agents, which is a common situation in practice. Now we are ready to state the first main result. The theorem establishes a correspondence between agent states and communities, by showing that most of the regular agents in the same community have states close to the initial average opinion of their communities within a transient time interval.
Theorem 1 Suppose that Assumptions 1-3 hold. Define the following set for ε ∈ (0, 1), Let τ 1 > 0 be any constant such that τ 1 log(r 0 n) ≥ 1. If there exist δ, γ ∈ (0, 1) such that then it holds that Remark 3 The set S ε t given in the theorem consists of regular agents that have states with small deviation, bounded by εc x , from the initial average opinion of the corresponding community at time t. The theorem states that the probability that such regular agents make up the majority of the network can be lower bounded by some constant, during the early stage of the process. In other words, most regular agents in the same community can have states close to the initial average opinion of that community with high probability.
s must be large enough to ensure that (5) holds and that the time interval given in the theorem exists. Intuitively this condition means that the edge weights within communities are much larger than weights between the two communities and weights between stubborn and regular agents. The parameter τ 1 can be arbitrarily small such that the transient interval starts at t = Θ(1/λ 3 ), but this event can only happen when n is large, because small τ 1 makes (2λ 3 /λ 2 ) 1/τ1 a large number.
Theorem 1 characterizes how gossip model (1) behaves at its early stage, by lower bounding the probability of the portion of regular agents, whose opinions concentrate around the initial average opinion of the corresponding community. The theorem shows a trade-off when bounding the concentration error: given a fixed network size n, to obtain a nontrivial bound, we need to set ε (the error of the concentration), δ (the portion of regular agents whose opinions do not concentrate), and γ (the probability that the concentration happens) all to be small enough, but, from the lower bound of their products (5), the three parameters cannot be arbitrarily small at the same time.
In Theorem 1, the relation between edge weights is hidden in the eigenvalues given in (5). To explicitly characterize the relative size of edge weights and show the effect of edge weights on the duration of the transient interval, we present the following corollary, which is a consequence of Theorem 1.
Then for S ε t given in Theorem 1 and any constants ε, δ, γ ∈ (0, 1), the following holds for large enough n

Remark 5
The corollary indicates that, if the intra-community weights are of higher order than the inter-community weights and weights between regular and stubborn agents, then most agent states concentrate around the initial average opinion of the corresponding community with high probability within the given transient time interval.

Remark 6
Since there are at most two agents updating at each time step, the number of updates for each regular agent in the time interval given in Corollary 1 is on average nl , which is the interaction strength of agents within a community relative to interaction strength between communities and that between regular and stubborn agents. When l (r) s decreases, the transient interval shrinks.
Our next result studies the case where the influence of stubborn agents is still relatively small compared with weights between regular agents, but the difference between inter-and intra-community weights is not so large.

Remark 7
The set T ε t given in the theorem contains regular agents that have opinions with small deviation from the initial average opinion of the entire network at time t. The theorem states that, if the difference between intraand inter-community weights is smaller than the average weights between regular and stubborn agents, then a large portion of regular agents can have states close to everyone's initial average opinion with high probability, during the initial phase of the process. This result shows that transient behavior of the gossip model, in the case where l d , which is studied in Theorem 1.

Remark 8
The assumption (6) given in Theorem 2 allows l (r) s to be slightly greater than l is not large enough to make regular agents in different communities stay away from each other. The assumption also allows that l (r) s < l (r) d (c 0 = 0 in this case), which corresponds to the disassortative community structure of a network [3]. Theorem 2 indicates that the gossip model reaches a transient global consensus in this case. As τ 1 in Theorem 1, the parameter τ 2 can be arbitrarily small (hence the beginning of the transient interval can be arbitrarily close to Θ(1/λ 3 )), but n needs to be large enough in this case. Theorem 2 implies that the phase transition of transient behavior of the gossip model occurs when l Similar to Theorem 1, the requirement of Theorem 2 for the relative size of weights between regular agents and those between regular and stubborn agents is hidden in (7). The next corollary provides an explicit condition for this relative size and characterizes how edge weights influence the duration of the transient interval.
Corollary 2 Suppose that Assumptions 1-3 hold. Further assume that there exists some c 0 ≥ 0 such that l (r) Then for T ε t given in Theorem 2 and any constants ε, δ, γ ∈ (0, 1), the following holds for large enough n

Remark 9
The corollary implies that, if the difference between intra-and inter-community weights is of the same order as the average weight between regular and stubborn agents, and the maximum of weights between regular agents is of higher order than those between regular and stubborn agents, then most of the regular agents have states concentrating around everyone's initial average opinion with high probability, within a transient time interval. The number of updates for each regular agent in the time interval given in Corollary 2 is n(l (r) The preceding two theorems study the case where the influence of stubborn agents is small. In the following, we show that, if the influence of stubborn agents is large, then agent opinions move quickly towards their steady states at the initial phase of the process.
It is known that gossip model (1) converges to a unique stationary distribution π (that is, if X(0) has distribution π, then X(t) has the same distribution for all t ∈ N + ), if at least one regular agent is connected to some stubborn agent and the network is connected [7,25]. Moreover, the stationary distribution π is the same as the distribution of the random series ∞ i=0 Q(0) · · · Q(i − 1)R(i)z s . From the definition of Q(t) and R(t), we know that the mean The following result provides the convergence rate of the expected agent states to their expected steady states. Proposition 1 Suppose that Assumptions 1-2 hold. Then, for all i ∈ V r and t ∈ N, it holds that PROOF. The conclusion follows from Lemma 2 and the fact (

Remark 10
The vector (I −Q) −1R z s is the expected stationary state vector, which is a linear combination of stubborn agents, of gossip model (1). The proposition shows that the expected agent states converge to the stationary states with rate of (1−λ 1 ) t . When the influence of stubborn agents is large (for example, (l (r) d ∨l (r) s )n = o(l (s) )), λ 1 , λ 2 , and λ 3 are of the same order. For an arbitrarily small constant ε > 0, it holds that . This observation implies that the expected states for all regular agents are close to the steady states from time t = Θ(n), if the influence of stubborn agents is large.
To further characterize the distance between transient and stationary distributions of agent states, we introduce the Wasserstein metric between two measures µ and ν, where J is the set of pairs of random vectors (X, Y ) such that the marginal distribution of X is µ and the marginal distribution of Y is ν. The following theorem provides the time interval in which the distribution of X(t) is close to π.

Remark 11
The theorem states that the distribution of X(t) is close to π after time Θ (log n)/λ 1 . Note that the time interval given in Theorem 1 ends at Θ(1/λ 2 ), whereas that given in Theorem 2 ends at Θ(1/λ 1 ). Hence Theorem 3 shows that, after forming transient clusters, regular agents move towards their steady states in the long run.
Theorem 3 provides a general characterization for behavior of the gossip model in the long run. The following corollary focuses on the case where the influence of stubborn agents is large.

Remark 12
Corollary 3 indicates that, if the influence of stubborn agents is large, then the distribution of X(t) can be arbitrarily close to the stationary distribution of the gossip model at the early stage of the process. Hence, under this situation, the concentration emerging from time t = n log n in Corollaries 1 and 2 cannot happen.
Example 3 Consider l (r) s = Θ((log β2 n)/n), l (r) d = Θ((log β3 n)/n), and l (s) = Θ(log β1 n), which means that the influence of stubborn agents on regular ones is large. Under this circumstance, 1/λ 1 , 1/λ 2 , and 1/λ 3 are of the same order Θ(n). So the time interval given in Theorem 3 also starts from time Θ(n log n). It is known that, for the gossip model, the expected stationary states are linear combinations of stubborn-agent states [25], and the system reaches a consensus if there are no stubborn agents [23,24]. The obtained results indicate that transient behavior of the model can be completely different from the asymptotic behavior, since the transient clusters only depend on the initial states and the edge weights between agents, if the influence of stubborn agents is relatively small. Additionally, Theorem 1 validate the intuition that transient clusters can appear over a network with community structure, by providing conditions ensuring their existence and duration. However, the difference between intra-and inter-community needs to be large enough to guarantee this phenomenon, otherwise a transient global may be reached, as Theorem 2 shows.
The preceding results hold for the gossip model over a weighted graph with two communities. For the gossip model over weighted graphs with multiple communities, the extension is not trivial. The major difficulty lies in how to characterize different level of edge weights between several communities. We will study this problem in the future. In Section 4.2 we provide a numerical example illustrating that the intuition behind Theorems 1 and 2 is still valid. That is, if intra-community weights are larger than inter-community ones, then agents in the same community reach a transient local consensus; if the opposite holds, then agents in different communities concentrate around the same value at the early stage of the process. Studying the gossip model over an SBM, as discussed in Remark 1, needs more careful analysis for the deviation of the random graph from its expected graph [48]. We do not pursue it in this paper due to page limit, but in Section 4.3 we present a numerical experiment to show that the gossip model over an SBM with two communities has transient behavior similar to that over a weighted graph.

Numerical Simulations
In this section, we conduct numerical simulations to validate the theoretical results obtained in Section 3. We first study the case where the gossip model evolves over a weighted graph with two communities, illustrating the probability bounds and the phase transition phenomenon. We then show that similar phenomena exist for the model over a weighted graph with multiple communities. Finally, the behavior of the gossip model over SBMs is studied, showing possible extensions of the theoretical results.

Gossip Model with Two Communities
In the first set of experiments, we demonstrate transient behavior of the gossip model described by Theorems 1-3. Set the size of the network n = 60, the bound of agent states c x = 1, and the portion of regular agents r 0 = 0.9. Generate the initial value X i (0) independently from uniform distribution on (0, 1) for all i ∈ V r1 , X j (0) independently from uniform distribution on (−1, 0) for all j ∈ V r2 , and set stubborn-agent states z s = [1 s0n/2 − 1 s0n/2 ].
To validate Theorem 1, we follow Example 1. In this case, the influence of stubborn agents is small, and intracommunity interactions are more frequently than inter-community ones. We set the edge weight between agents in the same community be l (r) s = (log 5 n)/n and the edge weight between communities be l (r) d = (log n)/n. The edge weights between regular and stubborn agents are set to be as follows: for all i ∈ V r1 , l (s) ij = (log 3.8 n)/n for 1 ≤ j ≤ s 0 n/2, and a ij = 0 for 1 + s 0 n/2 ≤ j ≤ s 0 n; for all i ∈ V r2 , l (s) ij = 0 for 1 ≤ j ≤ s 0 n/2, a ij = (log 3.8 n)/n for 1 + s 0 n/2 ≤ j ≤ s 0 n. Hence l (s) = (s 0 log 3.8 n)/2. This setting intuitively means that the first half of stubborn agents influence only V r1 , whereas the second half of stubborn agents influence only V r2 . We use this setting of influence structure of stubborn agents for all numerical experiments in this subsection. We choose the power 3.8 because, in this way, (λ 2 log n)/λ 3 = O(1/(log n) 0.2 ) = o(1). Note that the transient time interval given in Theorem 1 and Example 1 starts with Θ(n log n) ≈ 245. Fig. 2(a) shows that, around this time step, most of the agents in the same community have states close to the initial average opinion of the community, as stated in Theorem 1. However, in the long run, their opinions are driven by stubborn agents and reach steady states.
We note that asymptotic behavior of the system can be different from that demonstrated in Fig. 2(a). As an example, we set l (r) s = (log 5 n)/n and l (r) d = (log n) 1.68 /n. In addition, l (s) = (s 0 log n)/2. The reason to choose such l (r) d is that (log n) 1.68 /n ≈ (s 0 log 3.8 n)/2 for n = 60, so the effect of small n on system behavior can be ruled out. As can be observed from Fig. 2(b), the transient behavior is similar to the preceding case, but all agent states get close in the end. Under the conditions given in Fig. 2(a) and 2(b), it is possible to detect the community labels of agents out of state observations. More precisely, if several snapshots at the early stage of the process are available, then we may recover most of the labels with high probability by clustering the agent states, which can be implied by Theorem 1.
Next, we follow Theorem 2 and Example 2. In this case, the influence of stubborn agents is small, and intercommunity interactions are more frequently than intra-community ones. We set l (r) s = (log n)/n and l (r) d = (log 5 n)/n. The edge weights between regular and stubborn agents are set to be the same as the first experiment, and thus l (s) = (s 0 log 3.8 n)/2. As discussed in Theorem 2 and Example 2, within the same time interval as the preceding experiment, most agents have states close to the initial average opinion of the entire group, which is shown in Fig. 2(c). However, they cannot reach a global consensus and keep fluctuating in the long run, because of the presence of stubborn agents.
We then illustrate the case, in which the influence of stubborn agents is large, considered in Theorem 3 and Example 3. Set l (r) s = (log 1.68 n)/n, l (r) d = (log n)/n, andl (s) = (s 0 log 5 n)/2. Fig. 2(d) shows that no consensus is achieved at the transient phase of the process, and regular-agent states move quickly towards the positions of stubborn agents. Note that, in this case, behavior of agent states in the long run is similar to the behavior illustrated in Fig. 2(a) (that is, agent states are close to those of stubborn agents), but transient behavior of the former process is completely different from the latter.
In what follows we demonstrate the probability bounds given in Theorems 1-2. We first study the case with l (r) s = (log 5 n)/n, l (r) d = (log n)/n, and l (s) = (s 0 log 3.8 n)/2, where intra-community edge weights are large. We consider two networks with n = 60 and n = 500, respectively. For each network, the model is run for 200 times. Following the notation in Theorem 1, we consider the concentration error ε = 0.1 and 0.25, and the portion of non-concentrating agents δ = 0.5, 0.25, and 0.05, and estimate the probability 1 − γ that the concentration holds by computing Here S ε t (k) is the set S ε t at the k-th run, and S ε t is the set of agents that concentrate around the initial average opinion of their communities with error ε at time t. As shown in Fig. 3, the probability of the concentration increases with ε and δ. That is, if we assume larger concentration error ε and larger portion of non-concentrating agents δ, then the probability that the concentration happens is also larger. In addition, the concentration phenomenon becomes more significant, and the concentration probability increases, when n gets larger. The simulation also shows that the transient concentration starts from time step Ω(n), when n is large, as discussed in Remark 4. The ending time step of the transient concentration gets closer to the predicted time step n log 1.2 n as n increases.
We then consider the case with l Here T ε t (k) is the set T ε t at the k-th run, and T ε t is the set of agents that concentrate around the initial average opinion of the entire group with error ε at time t. Similar to the previous experiment, Fig. 4 shows that the concentration probability increases with the concentration error ε and the portion of non-concentrating agents δ, and the concentration probability gets larger as n grows. The experiment result also indicates that the transient cluster appears approximately from time step n, as discussed in Remark 8. After time step n log 1.2 n, which is the predicted ending of the transient interval given in Corollary 2, the concentration probability does not decrease but keeps fluctuating. An illustration of system behavior is shown in Fig. 2(c). This phenomenon could be related to properties of steady states, but here we do not discuss it in detail.  The color of a trajectory represents the community label of that agent (red represents Vr1, and blue represents Vr2). Now we show how the gossip model behaves when the influence of stubborn agents is large, by examining the evolution of the expected states discussed in Proposition 1. The case with l (r) s = (log 1.68 n)/n, l (r) d = (log n)/n, and l (s) = (s 0 log 5 n)/2 is considered. In addition, n is set to be 60. Fig. 5 shows that the expected states of regular agents converge quickly towards their steady states. According to Remark 10, the difference between an expected state and its limit is less than 0.2 after time step t = log(6c x /ε)/{log[1/(1 − λ 1 )]} ≈ 300, which can be observed from Fig. 5.
Finally, we conduct two experiments to demonstrate how the phase transition occurs when edge weights vary. In the first simulation, we set l (r) d = (log β2 n)/n = (log 5 n)/n and l (s) = log n, and consider l (r) s = (log β1 n)/n with β 1 = 1, . . . , 10. We run the gossip model for 50 times, for each value of β 1 and for n = 60, 500, 1000, 2000, and compute the difference d c = 2| i∈Vr1 X i (t) − i∈Vr2 X i (t)|/(r 0 n) with t = [n log n]. We choose this time step because it is the time when transient concentration happens, as shown in Fig. 3 and Fig. 4. The difference d c represents the difference between the averages of agent states in the two communities. The case d c = 1 means local concentration whereas d c = 0 represents global concentration. Fig. 6(a) presents the phase transition phenomenon (the effect becomes stronger as n grows). It shows that the local concentration appears when β 1 − β 2 > 1 (i.e., l   appears when β 1 − β 2 < 1, indicating a sharp transition. In the second simulation, we set l (r) s = (log n)/n and l (r) d = (log β2 n)/n = (log 5 n)/n, and consider l (s) = log β3 n with β 3 = 1, . . . , 10. This simulation examines the phase transition in the influence of stubborn agents. Under this circumstance, d c = 2 means regular agents have states close to stubborn ones, whereas d c = 0 represents the global concentration. Fig. 6(b) illustrates that the transition occurs at nl (s) d = Θ(l (s) ) (i.e., β 3 = β 2 ), as predicted by Corollary 3.

Gossip Model with Multiple Communities
In this section, we investigate transient behavior of the gossip model over a weighted graph with multiple communities by studying a special case. Consider the gossip model over a weighted graph with four communities V rk , 1 ≤ k ≤ 4, with equal size. Let n = 60, c x = 1, and r 0 = 14/15. Hence, |V rk | =ñ r = 14 for 1 ≤ k ≤ 4. Generate X i (0) independently from uniform distribution on (1 − k/2, 1 − (k − 1)/2) for all i ∈ V rk , 1 ≤ k ≤ 4, and generate the entries of z s from uniform    5. Behavior of expected states of the gossip model. When the influence of stubborn agents is large, the expected states of regular agents converge quickly to their steady states. The color of a trajectory represents the community label of that agent (red represents Vr1, and blue represents Vr2). The black lines represents the steady states. distribution on (−1, 1). In addition, we assume the graph has the following adjacency matrix l r2 1ñ r ,ñr l r2 1ñ r ,ñr l r2 1ñ r ,ñr l (s) 0 1ñ r ,ns l r2 1ñ r ,ñr l r1 1ñ r ,ñr − diag{l r1 1ñ r } l r2 1ñ r ,ñr l r2 1ñ r ,ñr l (s) 0 1ñ r ,ns l r2 1ñ r ,ñr l r2 1ñ r ,ñr l r2 1ñ r ,ñr − diag{l r2 1ñ r } l r1 1ñ r ,ñr l (s) 0 1ñ r ,ns l r2 1ñ r ,ñr l r2 1ñ r ,ñr l r1 1ñ r ,ñr l r2 1ñ r ,ñr − diag{l r2 1ñ r } l (s) 0 1ñ r ,ns 0ñ r ,ñr 0ñ r ,ñr 0ñ r ,ñr 0ñ r ,ñr 0ñ r ,ns   where 1 m,m := 1 m 1 T m , l r1 = (log 5 n)/n, l r2 = (log n)/n, l (s) 0 = (log n)/n, and n s = |V s |. In other words, agents in community 1 interact more often with each other than with other agents. So do agents in community 2. However, agents in community 3 (community 4) interact more often with those in community 4 (community 3) than with others. Fig. 7 shows that, during the initial phase of the process, agents in communities 1 and 2 have states close to the initial average opinion of their own communities, but agents in communities 3 and 4 have states close to the initial average opinion of communities 3 and 4. This observation is similar to that shown in Fig. 2. The observation indicates that transient properties discussed in Section 3 may also hold for graphs with multiple communities.

Gossip Model over SBM
In this section we consider the gossip model over an SBM with two communities. As introduced in Remark 1, the weighted graph considered in Section 3 is the expected version of an SBM. A formal defintion for an SBM with two communities is given as follows: let C i = 1 for i ∈ V r1 = {1, . . . , r 0 n/2} and C i = 2 for i ∈ V r2 = {1 + r 0 n/2, . . . , r 0 n}; then, for i, j ∈ V r , add {i, j} to E with probability l (r) s if C i = C j and i = j, and add {i, j} to E with probability l (r) In the experiment, we set n = 60, c x = 1, and r 0 = 0.9. Hence |V rk | = 27, k = 1, 2. Generate X i (0) independently from uniform distribution on (0, 1) for all i ∈ V r1 , X j (0) independently from uniform distribution on (−1, 0) for all j ∈ V r2 , and set stubborn-agent states z s = [1 s0n/2 −1 s0n/2 ]. Next, we generate the rest of the network  according to following rule. For i ∈ V 1 , {i, j} ∈ E with probability l (s) 0 for 1 + r 0 n ≤ j ≤ r 0 n + s 0 n/2, and {i, j} ∈ E for 1 + r 0 n + s 0 n/2 ≤ j ≤ n. For i ∈ V 2 , {i, j} ∈ E for 1 + r 0 n ≤ j ≤ r 0 n + s 0 n/2, and {i, j} ∈ E with probability l (s) 0 for 1 + r 0 n + s 0 n/2 ≤ j ≤ n. Three sets of parameters are considered: (i) l We add the coefficient s 0 to rule out the effect of small n on system behavior. These sets of parameters correspond to the cases with large intra-community weights, large inter-community weights, and large influence of stubborn agents studied in Section 4.1. Transient behavior of the model with these parameters is shown in Fig. 8. The transient behavior of the model over the SBM (illustrated in Fig. 8(a), 8(b), and 8(c)) is similar to their counterparts over the weighted graph with two communities (Fig. 2(a), 2(c), and 2(d)). These observations indicate that transient properties discussed in Section 3 may also hold for general graphs with community structure.

Conclusion
In this paper, we investigated transient behavior of the gossip model over a graph with community structure. For the model over a weighted graph with two communities, we established a sharp transition result: When edge weights within communities are large enough and weights between regular and stubborn agents are small enough, most agents in the same community have states close to the initial average opinion of that community at the early stage of the process. When the difference between intra-and inter-community weights is small enough or the inter-community weights are larger than the intra-community ones, most agents in the network have states close to everyone's initial average opinion at the early stage. In contrast, if weights between regular and stubborn agents is large enough, the distribution of agent states is close to the stationary distribution, at the beginning of the process. We then conducted several numerical experiments to validate these results, and showed extensions to multiple communities and SBMs. Future work includes to study the gossip model over general graphs, to investigate transient behavior of other models, and to link theoretical findings to empirical data.

Acknowledgment
This work was supported by the Knut & Alice Wallenberg Foundation and the Swedish Research Council.
Lemma 3 Suppose that Assumptions 1-3 hold. Then it holds for 0 < t ≤ 1/(4λ 2 ) and n ≥ 30 PROOF. We divide the proof into four steps. In step 1, we provide an upper bound and a lower bound for E{ X η (t) 2 }. An upper bound and a lower bound for E{ X ξ (t) 2 } are obtained in step 2. The lower bounds of E{ X η (t) 2 } and E{ X ξ (t) 2 } are used in step 3, which gives an upper bound for E{ X Γ (t) 2 }. In step 4 we put everything together and complete the proof.