Centrality-Weighted Opinion Dynamics:
Disagreement and Social Network Partition

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 scale-free 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, 8, 9, 10, 11, 12] and the references therein for an overview). The study of opinion dynamics [4, 5, 6] connects inherently to the study of distributed coordination or the consensus protocol (see for instance [13, 14, 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, 17, 18]. In addition, plenty of research papers have approached the modelling of opinion evolution from Bayesian update perspectives (see for instance, [19, 20, 21, 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, 27, 28, 29, 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 [32, 29], 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.

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].

Let $[n]:=\{1,...,n\}$. Let $\text{diag}(u)$ represent the diagonal matrix with the diagonal elements specified by the vector $u$. $\text{diag}^{\frac{1}{2}}(u)$ (resp. $\text{diag}^{-\frac{1}{2}}(u)$) denotes the diagonal matrix with diagonal elements given by $u(i)^{\frac{1}{2}},i\in[n]$ (resp. $u(i)^{-\frac{1}{2}},i\in[n]$). $\mathbf{1}$ denotes the $n$-dimensional column vector with all elements being one. For any matrix $A$, $A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$ to denote its transpose.

A square matrix $A$ is diagonalizable if there exist an invertible real matrix $P$ and a diagonal real matrix $\Lambda$ such that $A=P^{-1}\Lambda P$. An eigenvalue $\lambda$ of a matrix $A$ is defined as the complex or real number such that there exists a complex or real vector $v\neq 0$ satisfying $Av=\lambda v$. Then $v$ is called an eigenvector of $A$ associated with the eigenvalue $\lambda$. Let $I$ denote the identity matrix with an appropriate dimension. Then the algebraic multiplicity of an eigenvalue $\lambda$ of $A$ is defined as the multiplicity of $\lambda$ as a root of $\text{det}(\lambda I-A)$; the geometric multiplicity of an eigenvalue $\lambda$ is defined as the maximum number of linearly independent eigenvectors associated with $\lambda$, which can be computed by $n-\text{rank}(\lambda I-A)$ when $A$ is of dimension $n\times n$. In this paper, whenever we list the eigenvalues $\{\lambda_{1},\cdots,\lambda_{n}\}$ of a matrix, we always order the eigenvalues in a non-decreasing order, that is, $\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}.$

A graph $G=(V,E)$ is defined by the set of nodes $V$ and the set of edges $E\subset V\times 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\in[n]$ (that is, its adjacency matrix $A$ satisfies $A=A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$). $\mathcal{G}(A)$ denotes the graph with $A$ as the adjacency matrix and $[n]$ as the node set. $N_{i}:=\{j|(j,i)\in 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$.

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:

1. (i)

   Individuals on a social network communicate and change their own opinions in the direction to conform with those of their neighbours;

2. (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:

$$\tau\dot{x}_{i}=\sum_{j\in N_{i}}\frac{d_{j}}{\sum_{j\in N_{i}}a_{ij}d_{j}}a_{ij}(x_{j}-x_{i}),~{}~{}x_{i}(0)=x_{i0},~{}i\in[n]$$

(1)

where $d_{i}=\sum_{j\in N_{i}}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 $\tau>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=A\mathbf{1},~{}\text{i.e.,}~{}d_{i}=\sum_{j\in N_{i}}a_{ij},~{}i\in[n].$ Then the “influence matrix” for (1) is given by

$$\bar{A}=[\textup{diag}(h)]^{-1}A\textup{diag}(d),\quad\text{with}~{}h=Ad.$$

Clearly $\bar{A}$ is not necessarily symmetric. The corresponding Laplacian matrix of this weighted “influence matrix” $\bar{A}$ is then given by

$$\bar{L}\triangleq\textup{diag}(\bar{A}\mathbf{1})-\bar{A}=I_{n}-\bar{A},$$

where the last equality holds because

$$\bar{A}\mathbf{1}=[\textup{diag}(h)]^{-1}A\textup{diag}(d)\mathbf{1}=[\textup{diag}(Ad)]^{-1}Ad=\mathbf{1}.$$

(2)

We note that the Laplacian matrix $\bar{L}$ is different from normalized Laplacian matrices (by connection degrees) of $A$ which are typically given by

		$\displaystyle L_{n}\triangleq[\textup{diag}(d)]^{-1}(\textup{diag}(d)-A)=I_{n}-[\textup{diag}(d)]^{-1}A,$
		$\displaystyle L_{sn}\triangleq I_{n}-[\textup{diag}(d)]^{-\frac{1}{2}}A[\textup{diag}(d)]^{-\frac{1}{2}}.$

Denote $x=[x_{1},\ldots,x_{n}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$. Then the dynamics in (1) have the following compact representation

$$\tau\dot{x}=-\bar{L}x,\quad x(0)=x_{0}$$

(3)

where the Laplacian matrix $\bar{L}$ and the adjacency matrix $\bar{A}$ are respectively given by

$$\bar{L}=I_{n}-\bar{A},\quad\text{with}~{}\bar{A}=[\textup{diag}(Ad)]^{-1}A\textup{diag}(d).$$

If the underlying graph $\mathcal{G}(A)$ with the adjacency matrix $A$ is connected and undirected, then Proposition 1 implies that the long-term behaviour of the system model (3) reaches agreement as follows $\lim_{t\rightarrow\infty}x(t)=u_{1}(v_{1}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}x_{0})$ where $u_{1}=\frac{1}{\sqrt{n}}\mathbf{1}$ is the normalized right eigenvector of $\bar{L}$ and $v_{1}$ is the normalized left eigenvector of $\bar{L}$ that associated with the only zero eigenvalue $\lambda_{1}=0$. (See for instance [39]).

The conclusion in Proposition 2 on real eigenvalues for $\bar{A}$ and $\bar{L}$ may not hold when $A$ is not a symmetric matrix.

Henceforth we assume that $\mathcal{G}(A)$ with the adjacency matrix $A$ is undirected and connected. Based on Proposition 3, $\bar{L}$ is diagonalizable, and hence the solution to (1) is explicit given by

$$x(t)=\sum_{i=1}^{n}e^{-\frac{t}{\tau}\lambda_{i}}u_{i}(v_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}x_{0}),$$

(4)

where $v_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$ and $u_{i}$ represent respectively the left and right orthonormal eigenvectors of $\bar{L}$ associated with eigenvalue $\lambda_{i}$ (allowing repeated eigenvalues), $i\in[n]$.

The disagreement state is defined as the state projection into the subspace that is orthogonal to the agreement subspace $\textup{span}\{\mathbf{1}\}$ (which is equivalently $\textup{span}\{u_{1}\}$) in the opinion state space. Then the disagreement state of (4) is given by

$$x^{\textup{dis}}(t)=\sum_{i=2}^{n}u_{i}(v_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}x(t))=\sum_{i=2}^{n}e^{-\frac{t}{\tau}\lambda_{i}}u_{i}(v_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}x_{0}).$$

(5)

The disagreement state converges to the origin exponentially over time and the slowest rate is governed by the smallest non-zero eigenvalue $\lambda_{2}(\bar{L})$ of $\bar{L}$. Hence to approximately characterize the disagreement over networks, one may use the smallest non-zero eigenvalues $\lambda_{2}(\bar{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 $\lambda_{2}(\bar{L})$. The signs of this projected opinion state will cluster nodes into two groups.
Partition Algorithm (Social Choice Algorithm):

1. (S1)

   When $\lambda_{2}(\bar{L})$ has algebraic multiplicity 1, let

   $$s\triangleq u_{2}.$$

   When $\lambda_{2}(\bar{L})$ has algebraic multiplicity $m_{2}~{}(m_{2}\geq 2)$, let

   $$s\triangleq\sum_{\ell=1}^{m_{2}}u_{2}^{\ell}(v_{2}^{\ell}{}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}x_{0})$$

   (6)

   where $\{u_{2}^{\ell}\}_{\ell=1}^{d}$ (resp. $\{v_{2}^{\ell}{}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\}_{\ell=1}^{d}$) represents the set of right (resp. left) orthonormal eigenvectors of $\bar{L}$ associated with $\lambda_{2}(\bar{L})$, and $x_{0}$ denotes the initial state of opinions.

2. (S2)

   The signs of elements in $s$ separate the nodes in the network into two clusters as follows:

   $\displaystyle C_{1}=\{i:s(i)>0\},\quad$

   $\displaystyle C_{2}=\{i:s(i)\leq 0\}.$

The features of this partition algorithm for social networks (or social choice algorithm) include:

• •

  When the algebraic multiplicity of $\lambda_{2}(\bar{L})$ is $1$, the graph $\mathcal{G}(A)$ can be partitioned into the same two clusters regardless of the initial opinion state $x_{0}$ (if $x_{0}\neq 0$).

• •

  When the algebraic multiplicity of $\lambda_{2}(\bar{L})$ of $\bar{L}$ 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 $\mathcal{G}(A)$ into two clusters since $\sum_{i=1}^{n}s(i)=0$ always holds due to the fact that $u_{2}^{\ell}$ is orthogonal to the eigenvector $u_{1}=\frac{1}{\sqrt{n}}\mathbf{1}_{n}$ for all $\ell\in\{1,\ldots,m_{2}\}$.

• •

  The partition depends on the eigen direction associate with $\lambda_{2}(\bar{L})$ under the interpretation that the disagreement state projected into the disagreement subspace associated with $\lambda_{2}(\bar{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$.

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.

Following (2), each row of $\bar{A}$ sums up to one and hence $\bar{A}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$ 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}=\sum_{j=1}^{n}p_{kj}\bar{A}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}_{ji}=\sum_{j=1}^{n}p_{kj}\bar{A}_{ij}$ With probability (row) vector $p_{k}=[p_{k1},\ldots,p_{kn}]$, the probability transition is compactly characterized by

$$p_{k+1}=p_{k}\bar{A}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}.$$

(12)

This formulation follows the Degroot model [5] by specializing the influence matrix in [5] to be the degree-centrality-weighted matrix $\bar{A}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$ given by

$$\bar{A}_{ij}=\frac{d_{j}}{\sum_{j\in N_{i}}a_{ij}d_{j}}a_{ij},\quad i,j\in\{1,...,n\}.$$

The diversity of the possible opinions at time $k$ can be estimated based on the inverse of the entropy of $p_{k}$, that is, $D_{k}={E_{k}^{-1}},\text{where}~{}E_{k}=-\sum_{i=1}^{n}p_{ki}\log p_{ki}.$ If $\mathcal{G}(A)$ with the adjacency matrix $A$ is undirected and connected and $\bar{A}$ does not have eigenvalue $-1$, that is, the underlying Markov chain is irreducible and aperiodic, then $p_{\infty i}=\frac{1}{n}$ for all $i\in[n]$ and $D_{\infty}=(\log n)^{-1}$.

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:

1. (i)

   Individual on a social network communicate and change their own opinions in the direction to conform with those of their neighbours;

2. (ii)

   Each individual weights these influences from the neighbours based on their importance on the network quantified by the centrality vector $\rho$.

The dynamic model for opinion state evolution over a network is then given by

$$\tau\dot{x}_{i}=\sum_{j\in N_{i}}\frac{\rho_{j}}{\sum_{j\in N_{i}}a_{ij}\rho_{j}}a_{ij}(x_{j}-x_{i})$$

where $\rho_{i}>0$ is the centrality of node $i$ on the network (based on an appropriate choice of centrality), $\tau>0$ is an appropriate time constant, and $a_{ij}$ represents the connection from node $j$ to $i$. The centrality $\rho$ 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 $\rho_{i}$.

If $\rho_{i}>0$ for all $i\in[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 $\rho(\cdot)$ is time-varying or state-dependent, all the results in Propositions 1-3 hold as long as $\rho_{i}(\cdot)>0$ for all $i\in[n]$.