Computer Science Engineering
Computer Science-2021.gz:143285
Computer Science
d7c0fd9924d1b0d463409cfd102b113d2e3964ad
Centrality-Weighted Opinion Dynamics: Disagreement and Social Network Partition

This paper proposes a network model of opinion dynamics based on both the social network structure and network centralities. The conceptual novelty in this model is that the opinion of each individual is weighted by the associated network centrality in characterizing the opinion spread on social networks. Following a degree-centrality-weighted opinion dynamics model, we provide an algorithm to partition nodes of any graph into two and multiple clusters based on opinion disagreements. Furthermore, the partition algorithm is applied to real-world social networks including the Zachary karate club network [1] and the southern woman network [2] and these application examples indirectly verify the effectiveness of the degree-centrality-weighted opinion dynamics model. Finally, properties of general centrality-weighted opinion dynamics model are established.


A. Motivation and background
Posts on online social platforms, opinions of individuals in social networks, or ideas in research papers, tend to be weighted (or perceived) differently due to the heterogeneity of hyperlink networks, social connections, or citation structures. These differences may be influenced by the ranking in Google search, social importance in social networks, or citation counts in citation networks. Network centralities, which quantify how central nodes are in a network, play a natural role in the phenomenon of heterogeneous weights (in posts, opinions or ideas) in these examples above. In particular, centrality weights proportional to nodal connection degrees may appear naturally in networks (see for example the preferential attachment network-growth model [3] for scalefree networks). Network influence weighted by connection degrees may well represent an underlying natural principle in the evolution of opinions and influences on social networks.
The modelling of opinion dynamics dates back to the work of French [4] via agent-based models on directed graphs, the work of Degroot [5] based on Markov process and that of Friedkin and Johnsen [6] based on dynamical systems. There have been many useful variations based on these basic models (see for instance [7]- [12] and the references therein for an overview). The study of opinion dynamics [4]- [6] connects inherently to the study of distributed coordination or the consensus protocol (see for instance [13]- [15]), which employs locally the relative state differences among neighbours. In this type of modelling, it is typically assumed that the "influence matrix" or "influence network" is given beforehand. However the influence matrix is not necessarily the social network structure and to the best knowledge of the author, there lacks a systematic way of identifying the influence matrix from network structures in the study of opinion dynamics. A second type of models to study the mechanism of opinion evolution and decision-making on a social network is via the Ising model with state-dependent network interactions [16], and the large-scale network opinion analysis is based on statistical characterizations of the underlying opinions [17], [18]. For this type of models, it is quite difficult to obtain explicit solutions and one typically needs to rely on numerical simulations or mean-field approximations [16]- [18]. In addition, plenty of research papers have approached the modelling of opinion evolution from Bayesian update perspectives (see for instance, [19]- [22]). Readers are referred to [7], [12] for an overview of the extensive research in modelling opinion dynamics. In the current paper, the basic model of studying opinion dynamics over networks is based on [5], [6] Centralities have been employed in modelling opinion dynamics in various different ways. The work [23] studied the opinion formation problem by incorporating the Ising model with the page-rank centrality [24]. The paper [25] provided a dynamics update model based on Erdös-Rényi random graphs and centralities such as in-degree, closeness and page-rank centralities. A centrality notion as the asymptotic opinion state was studied in [10]. These papers, among others, are different from the current paper in both the model formulation and the use of centralities in modelling opinion dynamics.
Social choice problems based on network structures are essentially graph partition problems, which have been studied from various perspectives (see for instance [26]- [30]). Such problems also arise from image segmentation (see for instance [31] the references therein). Various approaches, such as minimal spanning tree methods [31], spectral partition [26], [28], modularity matrix approach [29], [32], have been used to solve graph partition problems (see [31], [33] for a survey of different methods). In particular, spectral partition forms an important heuristic method for partitioning graphs [28]. The study of graph spectral partition method started in 1970s in [34], [35] based on eigenvectors of adjacency matrices and in [36], [37] based on the Fielder eigenvector (i.e., the eigenvector associated with the smallest non-zero eigenvalue of the graph Laplacian). In this paper, a spectral partition based on the centrality-weighted network provides us an algorithm to partition social networks.

B. Contribution
We propose a simple and concrete procedure to build "influence networks" based on social network structures and network centralities for the modelling of opinion dynamics. Then following a degree-centrality-weighted opinion dynamics, we provide a method for network partitions based on the disagreements approximately represented by the projection of the opinion state in the most significant eigendirection that is orthogonal to agreement subspace. This partition method produces the exact result for the split of the Zachary's karate club network [1], which indirectly verifies the effectiveness of our degree-centrality-weighted opinion dynamics model. Compared to network partition algorithm in [29] based on modularity measure which also correctly characterizes the partition for the Zachary's karate club network [1], our method provides a different theoretical interpretation of the network partition based on the disagreement of opinions from a dynamical system point of view, and this explanation fits naturally into the context of the social choice problem in [1].

Notation and terminology
Let [n] := {1, ..., n}. Let diag(u) represent the diagonal matrix with the diagonal elements specified by the vector u. diag 1 2 (u) (resp. diag − 1 2 (u)) denotes the diagonal matrix with diagonal elements given by u(i) ). 1 denotes the n-dimensional column vector with all elements being one. For any matrix A, A ⊺ to denote its transpose.
A square matrix A is diagonalizable if there exist an invertible real matrix P and a diagonal real matrix Λ such that A = P −1 ΛP . An eigenvalue λ of a matrix A is defined as the complex or real number such that there exists a complex or real vector v = 0 satisfying Av = λv. Then v is called an eigenvector of A associated with the eigenvalue λ. Let I denote the identity matrix with an appropriate dimension. Then the algebraic multiplicity of an eigenvalue λ of A is defined as the multiplicity of λ as a root of det(λI − A); the geometric multiplicity of an eigenvalue λ is defined as the maximum number of linearly independent eigenvectors associated with λ, which can be computed by n − rank(λI − A) when A is of dimension n × n. In this paper, whenever we list the eigenvalues {λ 1 , · · · , λ n } of a matrix, we always order the eigenvalues in a non-decreasing order, that is, λ 1 ≤ λ 2 ≤ · · · ≤ λ n .
A graph G = (V, E) is defined by the set of nodes V and the set of edges E ⊂ V × V connecting the nodes. A weighted graph is a graph in which each edge is associated with a real number weight. Taking the node set [n], then a graph can be represented by its adjacency matrix A = [a ij ] where a ij denotes the weight from node j to node i. A graph is undirected if the connection weight from i to j is always equal to the weights from j to i for all i, j ∈ [n] (that is, its adjacency matrix A satisfies A = A ⊺ ). G(A) denotes the graph with A as the adjacency matrix and [n] as the node set. N i := {j|(j, i) ∈ E} denotes the (incoming) neighborhood of node i. A path (resp. directed path) from node i to j is defined as a finite or infinite sequence of edges which joins a sequence of distinct nodes (resp. and the directed edges are in the same direction). An undirected graph is connected if for every node pair on the graph one can identify a path. A directed graph is strongly connected if every node pair (i, j) on the graph has a directed path from i to j.

A. Degree-centrality-weighted opinion dynamics
Social conformity characterizes the phenomenon that individuals tends to change his/her behavior or response to conform with that of the group and it has supporting evidence in social and psychology studies (see for instance [38]). Considering social conformity, basic assumptions in our degree-centrality-weighted opinion dynamics model are as follows: (i) Individuals on a social network communicate and change their own opinions in the direction to conform with those of their neighbours; (ii) Each individual weights these influences from the neighbours based on their importance on the network in terms of the number of their connections.
Based on these basic assumptions, the dynamics for opinion evolution over a social network are then formulated as follows: (1) where d i = j∈Ni a ij is the degree (centrality) of node i on the network, a ij is social connection weight between nodes i and j (which can take a real value if the underlying social network is weighted, or 0-1 value if the underlying graph only characterizes the social network structure), and τ > 0 is a fixed time constant.
Let A = [a ij ] denote the adjacency matrix of the underlying graph. The degree centrality vector is given by d = A1, i.e., d i = j∈Ni a ij , i ∈ [n]. Then the "influence matrix" for (1) is given bȳ ClearlyĀ is not necessarily symmetric. The corresponding Laplacian matrix of this weighted "influence matrix"Ā is then given byL where the last equality holds becausē We note that the Laplacian matrixL is different from normalized Laplacian matrices (by connection degrees) of A which are typically given by Then the dynamics in (1) have the following compact representation where the Laplacian matrixL and the adjacency matrixĀ are respectively given bȳ

B. Properties of the influence matrixĀ and its LaplacianL
n 1 is the normalized right eigenvector ofL and v 1 is the normalized left eigenvector ofL that associated with the only zero eigenvalue λ 1 = 0. (See for instance [39]).

Proposition 2 (Appendix B) If the underlying graph G(A)
with the adjacency matrix A is connected and undirected, then all the eigenvalues ofĀ andL are real.

✷
The conclusion in Proposition 2 on real eigenvalues forĀ andL may not hold when A is not a symmetric matrix.

Proposition 3 (Appendix C) If the underlying graph G(A)
with the adjacency matrix A is connected and undirected, thenĀ andL are diagonalizable. ✷ Henceforth we assume that G(A) with the adjacency matrix A is undirected and connected. Based on Proposition 3,L is diagonalizable, and hence the solution to (1) is explicit given by where v ⊺ i and u i represent respectively the left and right orthonormal eigenvectors ofL associated with eigenvalue λ i (allowing repeated eigenvalues), i ∈ [n].

C. Network opinion partition algorithm
The disagreement state is defined as the state projection into the subspace that is orthogonal to the agreement subspace span{1} (which is equivalently span{u 1 }) in the opinion state space. Then the disagreement state of (4) is given by The disagreement state converges to the origin exponentially over time and the slowest rate is governed by the smallest non-zero eigenvalue λ 2 (L) ofL. Hence to approximately characterize the disagreement over networks, one may use the smallest non-zero eigenvalues λ 2 (L) and its associated left and right eigenvectors. The basic idea for the partition algorithm is then to analyze the opinion state projected into the subspace associated with the eigenvector(s) of λ 2 (L). The signs of this projected opinion state will cluster nodes into two groups.
When λ 2 (L) has algebraic multiplicity m 2 (m 2 ≥ 2), let where represents the set of right (resp. left) orthonormal eigenvectors ofL associated with λ 2 (L), and x 0 denotes the initial state of opinions.
(S2) The signs of elements in s separate the nodes in the network into two clusters as follows: The features of this partition algorithm for social networks (or social choice algorithm) include: • When the algebraic multiplicity of λ 2 (L) is 1, the graph G(A) can be partitioned into the same two clusters regardless of the initial opinion state x 0 (if x 0 = 0). • When the algebraic multiplicity of λ 2 (L) ofL is greater than 1, we need to take the initial opinion state x 0 into consideration when partitioning the network. • With any non-zero initial condition x 0 , the algorithm can always partition the nodes of G(A) into two clusters since n i=1 s(i) = 0 always holds due to the fact that u ℓ 2 is orthogonal to the eigenvector u 1 = 1 √ n 1 n for all ℓ ∈ {1, . . . , m 2 }.
• The partition depends on the eigen direction associate with λ 2 (L) under the interpretation that the disagreement state projected into the disagreement subspace associated with λ 2 (L) will eventually become relatively significant when the time is long enough. • The partition does not change over time since replacing x 0 by x(t) in (6) does not change the signs of the elements of s.
Remark 1 When accurate information on the initial opinion state x 0 and the time constant τ is available, one may characterize the exact evolution of the opinions and hence establish a time-varying partition of the nodes on the graph based on their disagreement states x dis i (t), i ∈ [n].
✷ Remark 2 When λ 2 (L) ofL has multiplicity more than one and x 0 is not known, then there is no decisive partition. A trivial example is the complete graph with n nodes (n > 2) and uniform weights. In this case, the multiplicity of λ 2 (L) is n − 1 and the signs of elements in s depends on x 0 , and hence there is no meaningful partition based on the graph structure only. ✷ D. Applications to real-world social networks 1) Application to Zachary's karate club network: During Zachary's study of the social structure in a karate club [1], a conflict between the administrator (node 34) and the instructor (node 1) divided the club into two groups. Each node on the network represents an individual person and edges represent their social interactions outside the club. In [1] based on maximum-flow-minimum-cut analysis of the unweighted network structure, all but one member (node 9) of the club were correctly assigned individuals to groups they actually joined after the split. Fig. 1: Zachary's karate club network structure and the two clusters following our partition algorithm. Square-shaped nodes belong to cluster C 1 and circle-shaped nodes belong to cluster C 2 . The sizes of the nodes are monotone with respect to the strength of their memberships to their own clusters.
An application of our partition algorithm to the unweighted Karate club network assigns nodes into two separate groups: as illustrated in Figure 1. This clustering result coincides exactly with the division in the actual situation [1] and provides the same clustering result based on the modularity approach in [29].
It is worth emphasizing that the Fielder eigenvector of the original social network G(A) would assign all but node 3 into the correct groups. This indicates that the degreecentrality-weighted influence matrixĀ provides a more accurate spectral clustering result than the underlying social network structure represented by A.
2) Application to the southern woman network: The southern women network structure is analyzed and clustered them into groups in [2] based on interviews of 18 women. These 18 women attended 14 events and the connections among them are characterized by the number of co-attended events. Our partition algorithms assign individuals to two groups which is the same bipartition result except one node (node Pearl) as those in [2] and [40]. The partition result is as follows: • Cluster C 1 characterized by square-shaped nodes consists of Dorothy, Flora, Helen, Katherina, Myra, Nora, Olivia, Sylvia, Verne; • Cluster C 2 characterized by circle-shaped nodes consists of Brenda, Charlotte, Eleanor, Evelyn, Frances, Laura, Pearl, Ruth, Theresa. as illustrated in Figure 2.
In contrast, the Fielder eigenvector of the original social network G(A) would partition nodes into two groups where one group only consists of Flora and Olivia, which is far from the real-world clustering result in [2]. This again indicates that the degree (centrality) weighted influence is important analyzing social network structures and opinion dynamics.

E. Network partition into multiple groups
There are two ways to partition the graph into multiple clusters: 1) iterative bipartition and 2) K-means. These two ways represent slightly different meanings of the partition.
1) Iterative bipartition: Without initial opinion states and time constant, the partition of nodes on the network into different groups can be carried out as follows: First, we partition the graph into two subgraphs following our partition algorithm. Then we partition each of the subgraphs via our same partition algorithm. This procedure continues until the multiplicity of second smallest eigenvalue of the Laplacian for any graph or subgraph is more than 1. We then create a partition algorithm that can partition the graph into multiple groups. One feature of this partition method is that the number of clusters is automatically determined from the partition procedure and there is no need to specify the number of clusters beforehand.
2) K-means: The vector s produced by our algorithm approximately quantifies the disagreement level of individuals on the network. If the number of partitions is fixed and known beforehand, we can implement the standard K-means [41] to cluster the approximate disagreement state values {s(i), i ∈ [n]}. We note that when λ 2 (L) has multiplicity more than 1, the initial opinion states x 0 is also needed. By clustering the disagreement states, we provide a partition of the nodes into different clusters, where different clusters represent nodes with different levels of disagreements. Furthermore, if both the time constant τ and the initial opinion states x 0 are known, then one can exactly characterize the evolution of the disagreement state and apply K-means to identify time-varying clusters.
F. Diversity of opinions 1) Opinion diversity energy: Consider the following the energy function E(·) : where L := diag(A1) − A. We note that here a ij instead of a ij is used. The opinion diversity energy at time t is then given by The opinion projected into the eigendirection associated with λ 2 (L) is given by and the associated diversity energy is then given by E(y 2 (t)) = 1 2 n i=1 n j=1 a ij (y 2i (t) − y 2j (t)) 2 = y 2 (t) ⊺ Ly 2 (t).
Remark 3 There may be other choices of the energy function E(·) with slightly different meanings, such as ✷ 2) Inverse entropy diversity: If λ 2 (L) has multiplicity 1, we may use the following approximate estimate of the opinion diversity in (10), without considering the underlying time constant τ and initial condition x 0 . An entropy associated with u 2 can be defined via where u 2 is the normalized Fiedler eigenvector (i.e., the normalized eigenvector with λ 2 (L)). The diversity of opinions (or the size of disagreement) on the graph G(Ā) can then be characterized by Since the property u 2 , 1 = 0 holds, the index takes into account the signs of u 2 implicitly. Roughly speaking, this index measures the diversity of the relative membership strengths of individuals to their own opinion groups. Following the idea of Inverse Simpson index, another diversity measure can be given by

G. The Markov chain interpretation
Following (2), each row ofĀ sums up to one and hencē A ⊺ can be associated to the probability transition matrix of a Markov chain. Let p ki represent the probability of individual i support an idea or an opinion at time k. Then the probability transition is characterized as follows: p (k+1)i = n j=1 p kjĀ ⊺ ji = n j=1 p kjĀij With probability (row) vector p k = [p k1 , . . . , p kn ], the probability transition is compactly characterized by This formulation follows the Degroot model [5] by specializing the influence matrix in [5] to be the degree-centralityweighted matrixĀ ⊺ given bȳ

Proposition 4 (Appendix D) If the underlying graph G(A)
with the adjacency matrix A is connected, then the Markov chain associated withĀ ⊺ as in (12) is irreducible and aperiodic if and only if −1 is not an eigenvalue ofĀ.

✷
The diversity of the possible opinions at time k can be estimated based on the inverse of the entropy of p k , that is, with the adjacency matrix A is undirected and connected andĀ does not have eigenvalue −1, that is, the underlying Markov chain is irreducible and aperiodic, then p ∞i = 1 n for all i ∈ [n] and D ∞ = (log n) −1 .

H. General centrality-weighted opinion dynamics
Centralities on a network, which typically depend on the network structures, quantify the importance of nodes on the network. The degree centrality explored in Section II-A is a particular choice of centrality. Other examples of centralities included betweenness, eigen-centrality, page-rank centrality, Sharply values, etc. For different types of networks, different centralities may be suitable to characterize the influence on information and opinion propagation.
Similar to the previous model in Section II-A, the basic assumptions for general centrality-weighted opinion dynamics include the following: (i) Individual on a social network communicate and change their own opinions in the direction to conform with those of their neighbours; (ii) Each individual weights these influences from the neighbours based on their importance on the network quantified by the centrality vector ρ.
The dynamic model for opinion state evolution over a network is then given by where ρ i > 0 is the centrality of node i on the network (based on an appropriate choice of centrality), τ > 0 is an appropriate time constant, and a ij represents the connection from node j to i. The centrality ρ should be chosen according to the underlying application problems, as different centralities may be suitable for different application problems. The Markov chain interpretation in (12) can also be generalized simply by replacing d i there by ρ i . If ρ i > 0 for all i ∈ [n], all the results in Propositions 1-4 hold for general centralities as well. The corresponding partition algorithm extends this this case naturally. Furthermore, one can verify that when the centrality ρ(·) is time-varying or state-dependent, all the results in Propositions 1-3 hold as long as ρ i (·) > 0 for all i ∈ [n].

III. CONCLUSIONS
This paper proposed an opinion dynamics model based on network structures and nodal centralities. The model was used to partition graphs into clusters.
Future work should include exploring more real-world examples on different types of social networks, studying similar models for directed graphs, and providing a systematic procedure to identify suitable centralities based on data (i.e., the learning of the suitable centrality on social networks). Moreover, the centrality may also be generalized to depend on the opinion states or some equilibrium states.

IV. ACKNOWLEDGEMENT
The author would like to thank Prof. Peter Caines for the helpful conversations.

APPENDIX PROOFS OF PROPOSITIONS 1-4
A. Proof of Proposition 1 PROOF One can easily verify thatL1 = 0, that is, 0 is an eigenvalue ofL. Based on Gershgorin disk theorem [42], among all points on the imaginary axis only the origin can be the eigenvalue ofL, and all the eigenvalues except 0 have strictly positive real parts. If any directed graph contains a rooted out-branching 1 , then the rank of the Laplacian matrix is n − 1 (see for instance [39]). In the current case, since A corresponds to an undirected and connected graph, we obtain that d i > 0 for all i and furthermore we note that A is the adjacency matrix of a strongly connected directed graph. ThereforeĀ corresponds to the adjacency matrix of a graph that contains a rooted out-branching. HenceL as the associated Laplacian matrix has only one zero eigenvalue.

B. Proof of Proposition 2
PROOF Let P = diag 1 2 (d) diag 1 2 (h). Since for any connected graph all the elements of d and those of h = Ad are non-zero, the inverse of P exists and is given by P −1 = diag − 1 2 (d) diag − 1 2 (h). Multiplying P and P −1 on the left and right side ofĀ yields Since A is symmetric, Q ⊺ AQ is also symmetric, and hence all the eigenvalues of Q ⊺ AQ are real. As is known that the similarity trans-formationĀ = P −1 (Q ⊺ AQ) P preserves all eigenvalues, we obtain that all the eigenvalues ofĀ are real. Sincē L = I n −Ā, the eigenvalues λ i (L) = 1 − λ i (Ā) for all i. Therefore all the eigenvalues ofL are also real.

C. Proof of Proposition 3
PROOF Recall from (13) that and Q ⊺ AQ is symmetric and obviously diagonalizable.

D. Proof of Proposition 4
PROOF Since G(A) is connected, G(Ā ⊺ ) is strongly connected and hence the Markov chain associated withĀ ⊺ is irreducible. The aperiodicity is equivalent the fact thatĀ ⊺ has only one eigenvalue that lies on the unit circle of the complex plane. Since all the eigenvalues ofĀ are real and 1 is always an eigenvector ofĀ, the aperiodicity is equivalent to that −1 is not an eigenvalue ofĀ.