Perturbative Expansion of the Fundamental Equation of Online User Dynamics for Describing Changes in Eigenfrequencies

The structure of an OSN is represented by a directed graph in which users are nodes and relationships between users are directed links. The directed graph is defined by node set $V=\{1,2,\dots,n\}$ and link set $E$; it is denoted by $\mathcal{G}(V,E)$. Each directed link $((i\rightarrow j)\in E)$ has link weight $w_{ij}>0$. The (weighted) adjacency matrix $\bm{\mathcal{A}}=[\mathcal{A}_{ij}]_{1\leq i,j\leq n}$ of directed graph $\mathcal{G}$ is defined as follows.

Next, we define the outgoing degree $d_{i}$ of node $i$ as $d_{i}:=\sum_{j\in\partial i}w_{ij}$ by summing the link weights $w_{ij}$ $(j\in\partial i)$ (where $\partial i$ represents the set of adjacent nodes of node $i$). The matrix in which the outgoing degrees of each node are arranged in diagonal components is called the outgoing degree matrix and is defined as $\bm{\mathcal{D}}:=\mathrm{diag}(d_{0},d_{1},...,d_{n-1})$. The Laplacian matrix is defined as $\bm{\mathcal{L}}:=\bm{\mathcal{D}}-\bm{\mathcal{A}}$ with the outgoing degree matrix $\bm{\mathcal{D}}$ and the adjacency matrix $\bm{\mathcal{A}}$.

While the Laplacian matrix of the undirected graph is a symmetric matrix, the Laplacian matrix of the directed graph is an asymmetric matrix. Therefore, the eigenvalues of the Laplacian matrix of an undirected graph are always real and non-negative due to the nature of the Laplacian matrix. On the other hand, the eigenvalues of the Laplacian matrix of a directed graph are not always real numbers, but the real parts of the eigenvalues are known to be non-negative [23].

The symmetrizable graph is a directed graph in which the Laplacian matrix representing the network structure can be transformed into a symmetric matrix by similarity transformation using a diagonal matrix with positive diagonal components. The characteristic of a symmetrizable graph is that the product of the link weights in the rightward and leftward paths of any closed path of the graph is equal.

Any directed graph can be decomposed into a symmetrizable graph and a one-way link graph having at most only one-directional link between each node [1]. However, it is known that the decomposition is, in general, not unique. An example of Laplacian matrix decomposition is shown in Figure 1.

Let the original Laplacian matrix be $\bm{\mathcal{L}}$, the symmetrizable Laplacian matrix after decomposition be $\bm{\mathcal{L}}_{0}$, and the Laplacian matrix corresponding to the one-way link graph be $\bm{\mathcal{L}}_{\mathrm{I}}$,

Then, the decomposition of Figure 1 can be written as follows:

This subsection briefly describes the oscillation model [1], a theoretical framework for modeling user dynamics in OSNs.

Consider an OSN with $n$ users, where $x_{i}(t)$ is the state of node (user) $i$ at time $t$. Let the state vector of the node be $\bm{x}(t):={}^{t}\!(x_{1}(t),\,\dots,\,x_{n}(t))$. In the oscillation model in OSNs, the equation describing online user dynamics is given as follows:

This is the wave equation on the network, where $\bm{\mathcal{L}}$ is the Laplacian matrix of the directed graph representing the structure of the OSN.

From the solution of this equation, we can derive the oscillation energy; its value gives a generalized measure of node centrality. Node centrality is the measure of the degree of importance or activity of each node in a network. Typical examples are degree centrality and betweenness centrality. In the oscillation model, if the link weights and initial values are chosen appropriately, it is known that the oscillation energy yields degree centrality and betweenness centrality, which can provide a unifying foundation for different kinds of node centrality [4]. Moreover, since oscillation energy represents the intensity of network activity, the phenomenon of divergence in oscillation energy under certain conditions corresponds to the phenomenon of divergence in the intensity of user activity, which can be interpreted as the occurrence of explosive user dynamics such as online flaming [5].

The behavior of solutions to the wave equation (3) is characterized by the eigenvalues of the Laplacian matrix, and it is known that the amplitude of the solution diverges when any of the eigenvalues are not real values. When the amplitude of the solution diverges, the oscillation energy also diverges, and this phenomenon can be thought of as an occurrence of explosive user dynamics such as online flaming.

Thus, the conditions for the occurrence of explosive user dynamics can be explained by the eigenvalues of the Laplacian matrix representing the OSN structure. Then, is it possible to understand the causal relationship between OSN structure and user dynamics in terms of what kind of network structure causes explosive user dynamics? To answer this question, we divide the structure of the OSN into two parts, one is that part of the network structure whose solution properties are well known, while the other is the remainder. In this case, it is desirable that the user dynamics of the entire OSN are given in an easily understandable form of causal relationships as expressed by the solutions to the equations obtained from the network structure with well-known properties and the solutions obtained from the remainder of the network structure. The method is briefly summarized below.

Consider the symmetrizable Laplacian matrix $\bm{\mathcal{L}}_{0}$ obtained by decomposing $\bm{\mathcal{L}}$ by (2), and the Laplacian matrix of the one-way link graph $\bm{\mathcal{L}}_{\mathrm{I}}$. Let $\bm{\Lambda}_{0}$ be the diagonalized matrix obtained from $\bm{\mathcal{L}}_{0}$, and let $\bm{\Lambda}=\bm{\Lambda}_{0}+\bm{\Lambda}_{\mathrm{I}}$ be the matrix yielded by applying the same diagonalizing transformation of $\bm{\mathcal{L}}_{0}$ to $\bm{\mathcal{L}}$. Then, equation (3) can be transformed as follows:

where $\bm{\Lambda}_{\mathrm{I}}$ is the matrix corresponding to the effect of the one-way link graph, and $\bm{\phi}(t)$ is the user’s state vector $\bm{x}(t)$ transformed according to the transformation of the equation.

When $\bm{\Lambda}_{\mathrm{I}}=\bm{\mathrm{O}}$, i.e., when $\bm{\mathcal{L}}_{\mathrm{I}}=\bm{\mathrm{O}}$, the transformed wave equation (4) is diagonalized. This means we have independent $n$ wave equations. In this case, since all its eigenvalues of $\bm{\Lambda}$ are real (and non-negative), explosive user dynamics does not occur. In other words, the user dynamics produced by the structure of $\bm{\mathcal{L}}_{0}$ corresponds to the solution of the equation whose properties are well known. Therefore, the emergence of explosive user dynamics is driven by the one-way link graph represented by $\bm{\Lambda}_{\mathrm{I}}$.

Diagonalizing the wave equation for the symmetrizable directed graph $\bm{\mathcal{L}}_{0}$ using $\bm{\Lambda}_{0}$ yields

let $\bm{\phi}_{0}(t)$ be the solution to this diagonalized wave equation. Also, let $\bm{\Phi}_{0}(t)$ be the $n\times n$ diagonal matrix whose diagonal components are the components of $\bm{\phi}_{0}(t)$. This satisfies the same diagonalized wave equation as $\bm{\phi}_{0}(t)$ as follows:

Since this is $n$ independent equations, the solution is simply obtained as follows:

Next, let $\bm{\phi}_{\mathrm{I}}$ be the solution to the equation for the one-way link graph described below, and check whether solution $\bm{\phi}(t)$ of the transformed wave equation (4) can be expressed in a product-form, as an easily understood structure, as shown by

As an initial condition, we set $\bm{\phi}(t)=\bm{\phi}_{\mathrm{I}}(0)$, that is, $\bm{\Phi}_{0}(t)=\bm{I}$. Considering the possibility of a product-form solution, we derive an equation with $\bm{\phi}_{\mathrm{I}}$ as a solution as follows:

Using the fact that $\bm{\Phi}_{0}(-t)=(\bm{\Phi}_{0}(t))^{-1}$, we obtain

Since the last equality does not hold, the attempt to obtain a product-form solution is not successful. This is because the wave equation is a second-order differential equation of time, which results in an extra cross-term. To solve this problem, we need to rewrite the wave equation as a first-order differential equation of time. At the same time, the solution to the rewritten first-order differential equation must also be a solution to the original second-order differential wave equation.

We solve this problem by introducing the following fundamental equation of the oscillation model:

where $\bm{\Omega}_{0}$ and $\bm{\Omega}_{\mathrm{I}}$ are $n\times n$ matrixes determined from $\bm{\Omega}_{0}^{2}=\bm{\Lambda}_{0}$, $(\bm{\Omega}_{0}+\bm{\Omega}_{\mathrm{I}})^{2}=\bm{\Lambda}$. $\bm{\Omega}_{\mathrm{I}}$ is the matrix that represents the effect of the one-way link graph and is the matrix that can be the cause of the explosive user dynamics. The solution can then be given as a product-form solution as follows:

Note that $\bm{\Psi}_{0}(t)$ and $\bm{\psi}_{I}(t)$ are solutions to the following equation:

where $\bm{\Psi}_{0}(t)$ is an $n\times n$ matrix with $\bm{\Psi}_{0}(0)=\bm{I}$. This is checked below. Substituting the product-form solution (7) into the fundamental equation (6), we get

and the product-form solution is the solution to the fundamental equation. Note that we used the fact that $\bm{\Psi}_{0}(-t)=(\bm{\Psi}_{0}(t))^{-1}$.

Solution $\bm{\psi}(t)$ of fundamental equation (6) also satisfies equation (4). This can be checked using (6) as follows:

Since the property of the fundamental equation (6) is that the influence of the network structure on the solution can be described by the product-form solution, we use perturbation theory to explicitly describe the influence of the one-way link graph when the Laplacian matrix of OSN is decomposed, see (2). Perturbation theory is an approach that finds approximate solutions by slightly changing a simple equation whose solution has well-known properties. As the equation and its solution with well-known properties are (8) and $\bm{\Phi}_{0}(t)$, respectively, the parameter that characterizes the strength of the influence of the one-way link graph is $\epsilon$. It is defined as

Depending on the value of $\epsilon$, $\bm{\Omega}(0)=\bm{\Omega}_{0}$, $\bm{\Omega}(1)=\bm{\Omega}$. Next, consider the fundamental equation with $\bm{\Omega}(\epsilon)$ as follows:

where the solution to this equation, $\bm{\psi}(\epsilon;t)$, is a vector that depends on parameter $\epsilon$, where $\bm{\psi}(0;t)=\bm{\psi}_{0}(t)$ and $\bm{\psi}(1;t)=\bm{\psi}(t)$. In perturbation theory, we investigate how $\bm{\psi}(\epsilon;t)$ for $\epsilon\not=0$ changes with respect to $\bm{\psi}_{0}(t)$ as a power series of $\epsilon$. The method is specified as follows.

The formal solution to (12) is $\bm{\psi}(t)=\exp(\mp\bm{\Omega}(\epsilon))\,\bm{\psi}(0)$, but $\bm{\Omega}(\epsilon)$ is not a diagonal matrix for $\epsilon>0$, so the solution cannot be expressed simply. For this reason, we introduce a procedure that offers expansion as a power series of $\epsilon$ as follows. First, for $\Delta t\ll 1$, if $t=N\,\Delta t$, we get

Next, the perturbative expansion of solution $\bm{\psi}(t)$ with $\epsilon$ is as follows:

Consider a solution of (14) for each power order of $\epsilon$. Since term $\epsilon^{0}$ is the case where $\bm{\Omega}_{\mathrm{I}}$ is not affected until time $t$, it corresponds to the term without $\epsilon$ in the binomial expansion of (13), so

and when $\Delta t\rightarrow 0$, we get

The term of $\epsilon^{1}$, when there is an effect of $\bm{\Omega}_{\mathrm{I}}$ at time $t_{1}=k_{1}\,\Delta t$, is written as

adding them up gives the difference at time $t_{1}$. When $\Delta t\rightarrow 0$, we get

The term of $\epsilon^{2}$, when affected by $\bm{\Omega}_{\mathrm{I}}$ at times $t_{1}=k_{1}\,\Delta t$ and $t_{2}=k_{2}\,\Delta t$ $(t_{1}<t_{2})$, is

adding them up gives the difference between time $t_{1}$ and $t_{2}$. When $\Delta t\rightarrow 0$, we get

For higher-order terms, we can generate the integrand in the same way and calculate $k$ multiple integrals to obtain the solution for $\epsilon^{k}$ order.

Hereafter, since both equations in (6) have the same structure, we examine the fundamental equation of

from the two equations in (6).

There are $n$ oscillation modes that emerge from the wave equation representing the user dynamics for a network with $n$ users. To understand the mechanism of perturbative expansion, we consider a model in which only three of the $n$ oscillation modes affect each other cyclically, as shown in Figure 2.

Omitting the independent oscillation modes, we focus only on the $3$ oscillation modes that affect each other as represented by the $3\times 3$ matrix, $\bm{\Omega}(\epsilon)$, as follows:

Now, we decompose $\bm{\Omega}(\epsilon)$ into a diagonal matrix and the remainder as follows:

We set the initial state as follows:

and consider $\psi_{1}(t)$ of node 1 on behalf of the state of nodes. The perturbative expansion by the effect of the non-diagonal component of $\epsilon\,\bm{\Omega}_{\mathrm{I}}$ is as follows:

Let us consider the contribution of each term for each order of $\epsilon$. Since there is no effect of $\bm{\Omega}_{\mathrm{I}}$, the contribution of the $\epsilon^{0}$ order is

Next, we consider the contribution of the $\epsilon^{1}$ order. Figure 3 shows the state transition corresponding to the contribution of the $\epsilon^{1}$ order; this type of diagram is called the Feynman diagram.

The contribution of the $\epsilon^{1}$ order is calculated as follows:

Figure 4 shows the Feynman diagram corresponding to the contribution of the $\epsilon^{2}$ order.

The contribution of the $\epsilon^{2}$ order is calculated as follows:

As shown above, we can consider the contribution of each order of $\epsilon$, and by calculating the contribution to higher orders and finding regularities, we can evaluate the perturbative expansion with regard to infinite orders.

As shown in (19) and (20), the results of the perturbative expansion become more complex as the order increases. However, by applying an appropriate representation, the perturbative calculation of $\epsilon^{n}$ order for $n$ can be summarized as follows:

where $\alpha_{n}$, $\beta_{n}$ and $\gamma_{n}$ are coefficients, and $[x]$ is the integer part of $x$. The index $\mu$ of $\psi_{\mu}(0)$ is $\mu=1$ for $n=3k$, $\mu=3$ for $n=3k+1$, and $\mu=2$ for $n=3k+2$. This form makes it easy to compare the results of perturbative calculations for different orders, and the regularity found through this form allows us to derive a perturbative expansion that takes account of up to infinite orders.

First, we describe the details of the transformation to the form of (21) using the result of the $\epsilon^{3}$ order perturbative calculation as an example. The contribution of the $\epsilon^{3}$ order is calculated according to the method in Sect. IV-A as follows:

By organizing (22) in the form of (21), the parts other than $\psi_{1}(0)$ are as follows:

Next, we transform the numerator so that it does not contain $\omega_{1}^{\prime}$, $\omega_{2}^{\prime}$, and $\omega_{3}^{\prime}$ (except for the exponent of the exponential function). Focusing on the first term of expression (23), the numerator $\left(2\omega_{1}^{\prime}-\omega_{2}^{\prime}-\omega_{3}^{\prime}\right)$ can be transformed as follows:

These terms are canceled by the denominator and are as follows:

This shows that the result of the third-order perturbation can be expressed in the form of (21). By transforming the numerator so as not to include $\omega_{1}^{\prime}$, $\omega_{2}^{\prime}$, and $\omega_{3}^{\prime}$, it becomes easier to compare the results of different orders.

So far, we have used third-order perturbations as an example. For higher-order perturbation contributions, higher-order $\omega_{1}^{\prime}$, $\omega_{2}^{\prime}$, and $\omega_{3}^{\prime}$ appear in the numerator. However, it is possible to remove $\omega_{1}^{\prime}$, $\omega_{2}^{\prime}$, and $\omega_{3}^{\prime}$ from the numerator by the same operation. To check this, we start by considering how $\alpha_{m}$ can be written for arbitrary $m$. Classifying the order of perturbation $n$ into the $3$ moduli, we consider the case where $n=3\,k$ (where $k$ denotes the number of state transitions). The cases where $n=3k+1$ and $n=3k+2$ are discussed later. Let the denominator of $\alpha_{n}$ be $(\omega_{1}^{\prime}-\omega_{2}^{\prime})^{n-k}\,(\omega_{3}^{\prime}-\omega_{1}^{\prime})^{n-k}$. Organizing the numerator by terms proportional to $(\mathrm{i}\,t)^{m}$ $(m=0,\,1,\,\dots,\,k)$, we obtain

where $r^{(\alpha)}_{lk}$ is a constant determined for each combination of $l$ and $k$. Similarly,

where $r^{(\beta)}_{lk}$ and $r^{(\gamma)}_{lk}$ are constants determined for each $l$ and $k$, respectively, and the empty sum is defined as $0$.

In (25)–(27), each term in the numerator can be reduced. Only the constants $r^{(\alpha)}_{lk}$, $r^{(\beta)}_{lk}$, or $r^{(\gamma)}_{lk}$ and $(\mathrm{i}t)^{m}$ remain in the numerator of each fraction after the reduction. Since expression (24) is in reduced form and corresponds to the part $k=1$, $m=0$ of expression (25), it can be written as two terms, $l=0$ and $l=k-m=1$. After transforming the numerator into a constant, each term is uniquely determined from the number of cycles of the state transition $k$, $l$ in expression (25), and the power $m$ of $\mathrm{i}t$. Accordingly, in the following, each term of $\alpha_{n}$ in expression (21), after transforming it so as not to include $\omega_{1}^{\prime}$, $\omega_{2}^{\prime}$, and $\omega_{3}^{\prime}$ in the numerator, is denoted as $T^{(n)}_{\alpha}(k,l,m)$. That is, it is defined as follows:

We denote $\beta_{n}$ and $\gamma_{n}$ as $T^{(n)}_{\beta}(k,l,m)$ and $T^{(n)}_{\gamma}(k,l,m)$, respectively. Using these terms, (21) can be written as follows:

Next, we explain regularities found in the results obtained by the transformation so that their numerators do not include $\omega_{1}^{\prime}$, $\omega_{2}^{\prime}$, or $\omega_{3}^{\prime}$, and generalize to an infinite order perturbative expansion.

In the following, we show expressions (21) for the third-, sixth-, and ninth-order perturbations and give details of regularities that can be found there. First, for the third-order perturbation, to simplify the expression, the quantity divided by $\psi_{1}(0)$ is shown as follows: