In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

The phenomenon known as social polarization, in which a social group splits into two or more groups, can cause division of the society by causing the radicalization of opinions and the spread of misinformation, is particularly significant in online communities. To develop technologies to mitigate the effects of polarization in online social networks, it is necessary to understand the mechanism driving its occurrence. There are some models of social polarization in which network structure and users' opinions change, based on the quantified opinions held by the users of online social networks. However, they are based on the interaction between users connected by online social networks. Current recommendation systems offer information from unknown users who are deemed to have similar interests. We can interpret this situation as being yielded non-local effects brought on by the network system, it is not based on local interactions between users. In this paper, based on the spectral graph theory, which can describe non-local effects in online social networks mathematically, we propose a model of polarization that user behavior and network structure change while influencing each other including non-local effects. We investigate the characteristics of the proposed model. Simultaneously, we propose an index to evaluate the degree of network polarization quantitatively, which is needed for our investigations.

As online social networks (OSNs) have become remarkably active, we often experience explosive user dynamics such as online flaming, which can significantly impact the real world. Since the rapidity with which online user dynamics propagates, countermeasures based on social analyses of the individuals who cause online flaming take too much time that timely measures cannot be taken. To consider immediate solutions without individuals' social analyses, a countermeasure technology for flaming phenomena based on the oscillation model, which describes online user dynamics, has been proposed. In this framework, the strength of damping to prevent online flaming was derived based on the wave equation of networks. However, the assumed damping strength was to be a constant independent of the frequency of user dynamics. Since damping strength may generally depend on frequency, it is necessary to consider such frequency dependence in user dynamics. In this paper, we derive the strength of damping required to prevent online flaming under the general condition that damping strength depends on the frequency of user dynamics. We also investigate the existence range of the Laplacian matrix's eigenvalues representing the OSN structure assumed from the real data of OSNs, and apply it to the countermeasure technology for online flaming.

Spectral graph theory provides an algebraic approach to investigate the characteristics of weighted networks using the eigenvalues and eigenvectors of a matrix (e.g., normalized Laplacian matrix) that represents the structure of the network. However, it is difficult to accurately represent the structures of large-scale and complex networks (e.g., social network) as a matrix. This difficulty can be avoided if there is a universality, such that the eigenvalues are independent of the detailed structure in large-scale and complex network. In this paper, we clarify Wigner's Semicircle Law for weighted networks as such a universality. The law indicates that the eigenvalues of the normalized Laplacian matrix of weighted networks can be calculated from a few network statistics (the average degree, average link weight, and square average link weight) when the weighted networks satisfy a sufficient condition of the node degrees and the link weights.

The explosive dynamics present in on-line social networks, typically represented by flaming phenomena, can have a serious impact on not only the sustainable operation of information networks but also on activities in the real world. In order to counter the flaming phenomenon, it is necessary to understand the mechanism underlying the generation of the flaming phenomena within an engineering framework. This paper discusses a new model of the generating mechanism of the flaming phenomena. Our previous study has shown that the cause of flaming phenomena can, by reference to an oscillation model on networks, be understood complex eigenvalues of the matrix formed to describe oscillating phenomena. In this paper, we show that the flaming phenomena can occur due to coupling between degenerated oscillation modes even if all the eigenvalues are real numbers. In addition, we investigate the generation process of flaming phenomena with respect to the initial phases of the degenerated oscillation modes.

Spectral graph theory, based on the adjacency matrix or the Laplacian matrix that represents the network topology and link weights, provides a useful approach for analyzing network structure. However, in large scale and complex social networks, since it is difficult to completely know the network topology and link weights, we cannot determine the components of these matrices directly. To solve this problem, we propose a method for indirectly determining the Laplacian matrix by estimating its eigenvalues and eigenvectors using the resonance of oscillation dynamics on networks.

Spectral graph theory gives an algebraic approach to the analysis of the dynamics of a network by using the matrix that represents the network structure. However, it is not easy for social networks to apply the spectral graph theory because the matrix elements cannot be given exactly to represent the structure of a social network. The matrix element should be set on the basis of the relationship between persons, but the relationship cannot be quantified accurately from obtainable data (e.g., call history and chat history). To get around this problem, we utilize the universality of random matrices with the feature of social networks. As such a random matrix, we use the normalized Laplacian matrix for a network where link weights are randomly given. In this paper, we first clarify that the universality (i.e., the Wigner semicircle law) of the normalized Laplacian matrix appears in the eigenvalue frequency distribution regardless of the link weight distribution. Then, we analyze the information propagation speed by using the spectral graph theory and the universality of the normalized Laplacian matrix. As a result, we show that the worst-case speed of the information propagation changes up to twice if the structure (i.e., relationship among people) of a social network changes.