Zhongzhi Zhang

Yuhao Yi, Zhongzhi Zhang, Stacy Patterson

The vast majority of real-world networks are scale-free, loopy, and sparse, with a power-law degree distribution and a constant average degree. In this paper, we study first-order consensus dynamics in binary scale-free networks, where vertices are subject to white noise. We focus on the coherence of networks characterized in terms of the $H_2$-norm, which quantifies how closely agents track the consensus value. We first provide a lower bound of coherence of a network in terms of its average degree, which is independent of the network order. We then study the coherence of some sparse, scale-free real-world networks, which approaches a constant. We also study numerically the coherence of Barabási-Albert networks and high-dimensional random Apollonian networks, which also converges to a constant when the networks grow. Finally, based on the connection of coherence and the Kirchhoff index, we study analytically the coherence of two deterministically-growing sparse networks and obtain the exact expressions, which tend to small constants. Our results indicate that the effect of noise on the consensus dynamics in power-law networks is negligible. We argue that scale-free topology, together with loopy structure, is responsible for the strong robustness with respect to noisy consensus dynamics in power-law networks.

Yi Qi, Zhongzhi Zhang, Yuhao Yi et al.

The hierarchical graphs and Sierpiński graphs are constructed iteratively, which have the same number of vertices and edges at any iteration, but exhibit quite different structural properties: the hierarchical graphs are non-fractal and small-world, while the Sierpiński graphs are fractal and "large-world". Both graphs have found broad applications. In this paper, we study consensus problems in hierarchical graphs and Sierpiński graphs, focusing on three important quantities of consensus problems, that is, convergence speed, delay robustness, and coherence for first-order (and second-order) dynamics, which are, respectively, determined by algebraic connectivity, maximum eigenvalue, and sum of reciprocal (and square of reciprocal) of each nonzero eigenvalue of Laplacian matrix. For both graphs, based on the explicit recursive relation of eigenvalues at two successive iterations, we evaluate the second smallest eigenvalue, as well as the largest eigenvalue, and obtain the closed-form solutions to the sum of reciprocals (and square of reciprocals) of all nonzero eigenvalues. We also compare our obtained results for consensus problems on both graphs and show that they differ in all quantities concerned, which is due to the marked difference of their topological structures.

Changan Liu, Xiaotian Zhou, Ahad N. Zehmakan et al.

Critical nodes in networks are extremely vulnerable to malicious attacks to trigger negative cascading events such as the spread of misinformation and diseases. Therefore, effective moderation of critical nodes is very vital for mitigating the potential damages caused by such malicious diffusions. The current moderation methods are computationally expensive. Furthermore, they disregard the fundamental metric of information centrality, which measures the dissemination power of nodes. We investigate the problem of removing $k$ edges from a network to minimize the information centrality of a target node $\lea$ while preserving the network's connectivity. We prove that this problem is computationally challenging: it is NP-complete and its objective function is not supermodular. However, we propose three approximation greedy algorithms using novel techniques such as random walk-based Schur complement approximation and fast sum estimation. One of our algorithms runs in nearly linear time in the number of edges. To complement our theoretical analysis, we conduct a comprehensive set of experiments on synthetic and real networks with over one million nodes. Across various settings, the experimental results illustrate the effectiveness and efficiency of our proposed algorithms.

Changan Liu, Changjun Fan, Zhongzhi Zhang

Maximizing influences in complex networks is a practically important but computationally challenging task for social network analysis, due to its NP- hard nature. Most current approximation or heuristic methods either require tremendous human design efforts or achieve unsatisfying balances between effectiveness and efficiency. Recent machine learning attempts only focus on speed but lack performance enhancement. In this paper, different from previous attempts, we propose an effective deep reinforcement learning model that achieves superior performances over traditional best influence maximization algorithms. Specifically, we design an end-to-end learning framework that combines graph neural network as the encoder and reinforcement learning as the decoder, named DREIM. Trough extensive training on small synthetic graphs, DREIM outperforms the state-of-the-art baseline methods on very large synthetic and real-world networks on solution quality, and we also empirically show its linear scalability with regard to the network size, which demonstrates its superiority in solving this problem.

Wanyue Xu, Yubo Sun, Mingzhe Zhu et al.

The phenomenon of opinion disagreement has been empirically observed and reported in the literature, which is affected by various factors, such as the structure of social networks. An important discovery in network science is that most real-life networks, including social networks, are scale-free and sparse. In this paper, we study noisy opinion dynamics in sparse scale-free social networks to uncover the influence of power-law topology on opinion disagreement. We adopt the popular discrete-time DeGroot model for opinion dynamics in a graph, where nodes' opinions are subject to white noise. We first study opinion disagreement in many realistic and model networks with a scale-free topology, which approaches a constant, indicating that a scale-free structure is resistant to noise in the opinion dynamics. Moreover, existing algorithms for estimating opinion disagreement are computationally impractical for large-scale networks due to their high computational complexity. To solve this challenge, we introduce a sublinear-time algorithm to approximate this quantity with a theoretically guaranteed error. This algorithm efficiently simulates truncated random walks starting from a subset of nodes while preserving accurate estimation. Extensive experiments demonstrate its efficiency, accuracy, and scalability.

Changan Liu, Haoxin Sun, Ahad N. Zehmakan et al.

We study the notion of unfairness in social networks, where a group such as females in a male-dominated industry are disadvantaged in access to important information, e.g. job posts, due to their less favorable positions in the network. We investigate a well-established network-based formulation of fairness called PageRank fairness, which refers to a fair allocation of the PageRank weights among distinct groups. Our goal is to enhance the PageRank fairness by modifying the underlying network structure. More precisely, we study the problem of maximizing PageRank fairness with respect to a disadvantaged group, when we are permitted to rewire a fixed number of edges in the network. Building on a greedy approach, we leverage techniques from fast sampling of rooted spanning forests to devise an effective linear-time algorithm for this problem. To evaluate the accuracy and performance of our proposed algorithm, we conduct a large set of experiments on various real-world network data. Our experiments demonstrate that the proposed algorithm significantly outperforms the existing ones. Our algorithm is capable of generating accurate solutions for networks of million nodes in just a few minutes.

Ahad N. Zehmakan, Xiaotian Zhou, Zhongzhi Zhang

Consider a directed network where each node is either red (using the red product), blue (using the blue product), or uncolored (undecided). Then in each round, an uncolored node chooses red (resp. blue) with some probability proportional to the number of its red (resp. blue) out-neighbors. What is the best strategy to maximize the expected final number of red nodes given the budget to select $k$ red seed nodes? After proving that this problem is computationally hard, we provide a polynomial time approximation algorithm with the best possible approximation guarantee, building on the monotonicity and submodularity of the objective function and exploiting the Monte Carlo method. Furthermore, our experiments on various real-world and synthetic networks demonstrate that our proposed algorithm outperforms other algorithms. Additionally, we investigate the convergence time of the aforementioned process both theoretically and experimentally. In particular, we prove several tight bounds on the convergence time in terms of different graph parameters, such as the number of nodes/edges, maximum out-degree and diameter, by developing novel proof techniques.

Changan Liu, Zixuan Xie, Ahad N. Zehmakan et al.

Random walk centrality is a fundamental metric in graph mining for quantifying node importance and influence, defined as the weighted average of hitting times to a node from all other nodes. Despite its ability to capture rich graph structural information and its wide range of applications, computing this measure for large networks remains impractical due to the computational demands of existing methods. In this paper, we present a novel formulation of random walk centrality, underpinning two scalable algorithms: one leveraging approximate Cholesky factorization and sparse inverse estimation, while the other sampling rooted spanning trees. Both algorithms operate in near-linear time and provide strong approximation guarantees. Extensive experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.

Qi Bao, Zhongzhi Zhang, Haibin Kan

As a fundamental issue in network analysis, structural node similarity has received much attention in academia and is adopted in a wide range of applications. Among these proposed structural node similarity measures, role similarity stands out because of satisfying several axiomatic properties including automorphism conformation. Existing role similarity metrics cannot handle top-k queries on large real-world networks due to the high time and space cost. In this paper, we propose a new role similarity metric, namely \textsf{ForestSim}. We prove that \textsf{ForestSim} is an admissible role similarity metric and devise the corresponding top-k similarity search algorithm, namely \textsf{ForestSimSearch}, which is able to process a top-k query in $O(k)$ time once the precomputation is finished. Moreover, we speed up the precomputation by using a fast approximate algorithm to compute the diagonal entries of the forest matrix, which reduces the time and space complexity of the precomputation to $O(ε^{-2}m\log^5{n}\log{\frac{1}ε})$ and $O(m\log^3{n})$, respectively. Finally, we conduct extensive experiments on 26 real-world networks. The results show that \textsf{ForestSim} works efficiently on million-scale networks and achieves comparable performance to the state-of-art methods.

Stacy Patterson, Yuhao Yi, Zhongzhi Zhang

We study the performance of leader-follower noisy consensus networks, and in particular, the relationship between this performance and the locations of the leader nodes. Two types of dynamics are considered (1) noise-free leaders, in which leaders dictate the trajectory exactly and followers are subject to external disturbances, and (2) noise-corrupted leaders, in which both leaders and followers are subject to external perturbations. We measure the performance of a network by its coherence, an $H_2$ norm that quantifies how closely the followers track the leaders' trajectory. For both dynamics, we show a relationship between the coherence and resistance distances in an a electrical network. Using this relationship, we derive closed-form expressions for coherence as a function of the locations of the leaders. Further, we give analytical solutions to the optimal leader selection problem for several special classes of graphs.