Identifying multiple influential spreaders in complex networks based on spectral graph theory

One of the hot research topics in propagation dynamics is identifying a set of critical nodes that can influence maximization in a complex network.The importance and dispersion of critical nodes among them are both vital factors that can influence maximization.We therefore propose a multiple influential spreaders identification algorithm based on spectral graph theory.This algorithm first quantifies the role played by the local structure of nodes in the propagation process,then classifies the nodes based on the eigenvectors of the Laplace matrix,and finally selects a set of critical nodes by the constraint that nodes in the same class are not adjacent to each other while different classes of nodes can be adjacent to each other.Experimental results on real and synthetic networks show that our algorithm outperforms the state-of-the-art and classical algorithms in the SIR model.

Nonsmooth critical point theory and applications to the spectral graph theory

Existing critical point theories including metric and topological critical point theories are difficult to be applied directly to some concrete problems in particular polyhedral settings,because the notions of critical sets could be either very vague or too large.To overcome these difficulties,we develop the critical point theory for nonsmooth but Lipschitzian functions defined on convex polyhedrons.This yields natural extensions of classical results in the critical point theory,such as the Liusternik-Schnirelmann multiplicity theorem.More importantly,eigenvectors for some eigenvalue problems involving graph 1-Laplacian coincide with critical points of the corresponding functions on polytopes,which indicates that the critical point theory proposed in the present paper can be applied to study the nonlinear spectral graph theory.

Cheeger's cut, maxcut and the spectral theory of1-Laplacian on graphs

This is primarily an expository paper surveying up-to-date known results on the spectral theory of1-Laplacian on graphs and its applications to the Cheeger cut, maxcut and multi-cut problems. The structure of eigenspace, nodal domains, multiplicities of eigenvalues, and algorithms for graph cuts are collected.

Spectral Gap of the Largest Eigenvalue of the Normalized Graph Laplacian

We offer a new method for proving that the maxima eigenvalue of the normalized graph Laplacian of a graph with n vertices is at least n+1/n−1 provided the graph is not complete and that equality is attained if and only if the complement graph is a single edge or a complete bipartite graph with both parts of size n−1/2.With the same method,we also prove a new lower bound to the largest eigenvalue in terms of the minimum vertex degree,provided this is at most n−1/2.

THE 1-LAPLACIAN CHEEGER CUT： THEORY AND ALGORITHMS

This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend （CD） framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power （IP） method and the steepest descent （SD） method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.

Non-bipartite Graphs with Third Largest Laplacian Eigenvalue Less Than Three

All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.

GRAPHS CHARACTERIZED BY LAPLACIAN EIGENVALUES

This paper characterizes all connected graphs with exactly two Laplacian eigenval-ues greater than two and all connected graphs with exactly one Laplacian eigenvalue greater than three.

CONVERGENCE OF A CLASS OF MULTI-AGENT SYSTEMS IN PROBABILISTIC FRAMEWORK

Multi-agent systems arise from diverse fields in natural and artificial systems, and a basic problem is to understand how locally interacting agents lead to collective behaviors （e.g., synchronization） of the overall system. In this paper, we will consider a basic class of multi-agent systems that are described by a simplification of the well-known Vicsek model. This model looks simple, but the rigorous theoretical analysis is quite complicated, because there are strong nonlinear interactions among the agents in the model. In fact, most of the existing results on synchronization need to impose a certain connectivity condition on the global behaviors of the agents＇ trajectories （or on the closed-loop dynamic neighborhood graphs）, which are quite hard to verify in general. In this paper, by introducing a probabilistic framework to this problem, we will provide a complete and rigorous proof for the fact that the overall multi-agent system will synchronize with large probability as long as the number of agents is large enough. The proof is based on a detailed analysis of both the dynamical properties of the nonlinear system evolution and the asymptotic properties of the spectrum of random geometric graphs.