About Me

About Me

AP @ School of Business and Management, SISU

Sitemap

A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.

Pages

Posts

Future Blog Post

less than 1 minute read

Published:

This post will show up by default. To disable scheduling of future posts, edit config.yml and set future: false.

Blog Post number 4

less than 1 minute read

Published:

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 3

less than 1 minute read

Published:

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 2

less than 1 minute read

Published:

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 1

less than 1 minute read

Published:

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

portfolio

publications

Power-Law Graphs Have Minimal Scaling of Kemeny Constant for Random Walks

Published in Proceedings of the Web Conference (WWW 2020), Taipei, China, 2020

The mean hitting time from a node i to a node j selected randomly according to the stationary distribution of random walks is called the Kemeny constant, which has found various applications. It was proved that over all graphs with N vertices, complete graphs have the exact minimum Kemeny constant, growing linearly with N. Here we study numerically or analytically the Kemeny constant on many sparse real-world and model networks with scale-free smallworld topology, and show that their Kemeny constant also behaves linearly with N. Thus, sparse networks with scale-free and small-world topology are favorable architectures with optimal scaling of Kemeny constant. We then present a theoretically guaranteed estimation algorithm, which approximates the Kemeny constant for a graph in nearly linear time with respect to the number of edges. Extensive numerical experiments on model and real networks show that our approximation algorithm is both efficient and accurate.

Recommended citation: Xu Wanyue, Sheng Yibin, Zhang Zuobai, Kan Haibin, and Zhang Zhongzhi. Power-law graphs with minimal scaling of Kemeny constant for random walks. In: Proceedings of the Web Conference (WWW 2020), Taipei, China, April 20-24, 2020, pp.46-56. http://vivian1tsui.github.io/files/KemenyConstant.pdf

Nearly Linear Time Algorithm for Mean Hitting Times of Random Walks on a Graph

Published in Proceedings of the 13th International Conference on Web Search and Data Mining(WSDM), 2020

For random walks on a graph, the mean hitting time $H_j$ from a vertex i chosen from the stationary distribution to the target vertex j can be used as a measure of importance for vertex j, while the Kemeny constant K is the mean hitting time from a vertex i to a vertex j selected randomly according to the stationary distribution. Both quantities have found a large variety of applications in different areas. However, their high computational complexity limits their applications, especially for large networks with millions of vertices. In this paper, we first establish a connection between the two quantities, representing K in terms of $H_j$ for all vertices. We then express both quantities in terms of quadratic forms of the pseudoinverse for graph Laplacian, based on which we develop an efficient algorithm that provides an approximation of $H_j$ for all vertices and K in nearly linear time with respect to the edge number, with high probability. Extensive experiment results on real-life and model networks validate both the efficiency and accuracy of the proposed algorithm.

Recommended citation: Zhang Zuobai, Xu Wanyue, and Zhang Zhongzhi. Nearly linear time algorithm for mean hitting times of random walks on a graph. In: Proceedings of ACM International Conference on Web Search and Data Mining (WSDM 2020), Houston, USA, February 3-7, 2020, pp.726-734. http://vivian1tsui.github.io/files/WSDM2020.pdf

Fast Approximation of Coherence for Second-Order Noisy Consensus Networks

Published in IEEE Transactions on Cybernetics, 2020

It has been recently established that for second-order consensus dynamics with additive noise, the performance measures, including the vertex coherence and network coherence defined, respectively, as the steady-state variance of the deviation of each vertex state from the average and the average steady-state variance of the system, are closely related to the biharmonic distances. However, direct computation of biharmonic distances is computationally infeasible for huge networks with millions of vertices. In this article, leveraging the implicit fact that both vertex and network coherence can be expressed in terms of the diagonal entries of pseudoinverse LL2† of the square of graph Laplacian, we develop a nearly linear-time algorithm to approximate all diagonal entries of LL2†, which has a theoretically guaranteed error for each diagonal entry. The key ingredient of our approximation algorithm is an integration of the Johnson-Lindenstrauss lemma and Laplacian solvers. Extensive numerical experiments on real-life and model networks are presented, which indicate that our approximation algorithm is both efficient and accurate and is scalable to large-scale networks with millions of vertices.

Recommended citation: Zhang Zuobai, Xu Wanyue, Yi Yuhao, and Zhang Zhongzhi. Fast approximation of coherence for second-order noisy consensus networks. IEEE Transactions on Cybernetics, 2020. http://vivian1tsui.github.io/files/2ndFastApproximation.pdf

Opinion dynamics incorporating higher-order interactions

Published in Proceedings of 2020 IEEE International Conference on Data Mining (ICDM), Sorrento, Italy, 2020

The issue of opinion sharing and formation has received considerable attention in the academic literature, and a few models have been proposed to study this problem. However, existing models are limited to the interactions among nearest neighbors, ignoring those second, third, and higher-order neighbors, despite the fact that higher-order interactions occur frequently in real social networks. In this paper, we develop a new model for opinion dynamics by incorporating long-range interactions based on higher-order random walks. We prove that the model converges to a fixed opinion vector, which may differ greatly from those models without higher-order interactions. Since direct computation of the equilibrium opinions is computationally expensive, which involves the operations of huge-scale matrix multiplication and inversion, we design a theoretically convergence-guaranteed estimation algorithm that approximates the equilibrium opinion vector nearly linearly in both space and time with respect to the number of edges in the graph. We conduct extensive experiments on various social networks, demonstrating that the new algorithm is both highly efficient and effective.

Recommended citation: Zhang Zuobai, Xu Wanyue, and Zhang Zhongzhi, and Chen Guanrong. Opinion dynamics incorporating higher-order interactions. In: Proceedings of the 20th IEEE International Conference on Data Mining (ICDM 2020), Sorrento, Italy, November 17-20, 2020, pp.1430-1435. http://vivian1tsui.github.io/files/ICDM2020.pdf

Real-World Networks Are Not Always Fast Mixing

Published in The Computer Journal, 2020

The mixing time of random walks on a graph has found broad applications across both theoretical and practical aspects of computer science, with the application effects depending on the behavior of mixing time. It is extensively believed that real-world networks, especially social networks, are fast mixing with their mixing time at most O(logN) where N is the number of vertices. However, the behavior of mixing time in the real-life networks has not been examined carefully, and exactly analytical research for mixing time in models mimicking real networks is still lacking. In this paper, we first experimentally evaluate the mixing time of various real-world networks with scale-free small-world properties and show that their mixing time is much higher than anticipated. To better understand the behavior of the mixing time for real-world networks, we then analytically study the mixing time of the Apollonian network, which is simultaneously scale-free and small-world. To this end, we derive the recursive relations for all eigenvalues, especially the second largest eigenvalue modulus of the transition matrix, based on which we deduce a lower bound for the mixing time of the Apollonian network, which approximately scales sublinearly with N⁠. Our results indicate that real-world networks are not always fast mixing, which has potential implications in the design of algorithms related to mixing time.

Recommended citation: Qi Yi, Xu Wanyue, Zhu Liwang, and Zhang Zhongzhi. Real-world networks are not always fast mixing. The Computer Journal, 2021, 64(2):236-244. http://vivian1tsui.github.io/files/CompJMixing.pdf

Coherence Scaling of Noisy Second-order Scale-free Consensus Networks

Published in IEEE Transactions on Cybernetics, 2021

A striking discovery in the field of network science is that the majority of real networked systems have some universal structural properties. In general, they are simultaneously sparse, scale-free, small-world, and loopy. In this article, we investigate the second-order consensus of dynamic networks with such universal structures subject to white noise at vertices. We focus on the network coherence HSO characterized in terms of the H₂-norm of the vertex systems, which measures the mean deviation of vertex states from their average value. We first study numerically the coherence of some representative real-world networks. We find that their coherence HSO scales sublinearly with the vertex number N. We then study analytically HSO for a class of iteratively growing networks–pseudofractal scale-free webs (PSFWs), and obtain an exact solution to HSO, which also increases sublinearly in N, with an exponent much smaller than 1. To explain the reasons for this sublinear behavior, we finally study HSO for Sierpinśki gaskets, for which HSO grows superlinearly in N, with a power exponent much larger than 1. Sierpinśki gaskets have the same number of vertices and edges as the PSFWs but do not display the scale-free and small-world properties. We thus conclude that the scale-free, small-world, and loopy topologies are jointly responsible for the observed sublinear scaling of HSO.

Recommended citation: Xu Wanyue, Wu Bin, Zhang Zuobai, Zhang Zhongzhi, Kan Haibin, and Chen Guanrong. Coherence scaling of noisy second-order scale-free consensus networks. IEEE Transactions on Cybernetics, 2021. http://vivian1tsui.github.io/files/2ndConsensus.pdf

Benchmark for Discriminating Power of Edge Centrality Metrics

Published in The Computer Journal, 2021

Edge centrality has found wide applications in various aspects. Many edge centrality metrics have been proposed, but the crucial issue that how good the discriminating power of a metric is, with respect to other measures, is still open. In this paper, we address the question about the benchmark of the discriminating power of edge centrality metrics. We first use the automorphism concept to define equivalent edges, based on which we introduce a benchmark for the discriminating power of edge centrality measures and develop a fast approach to compare the discriminating power of different measures. According to the benchmark, for a desirable measure, equivalent edges have identical metric scores, while inequivalent edges possess different scores. However, we show that even in a toy graph, inequivalent edges cannot be discriminated by three existing edge centrality metrics. We then present a novel edge centrality metric called forest centrality. Extensive experiments on real-world networks and model networks indicate that forest centrality has better discriminating power than three existing edge centrality metrics.

Recommended citation: Bao Qi, Xu Wanyue, and Zhang Zhongzhi. Benchmark for discriminating power of edge centrality metrics. The Computer Journal, 2021. http://vivian1tsui.github.io/files/CompJBenchmark.pdf

Fast Evaluation for Relevant Quantities of Opinion Dynamics

Published in Proceedings of the Web Conference (WWW 2021), Ljubljana, Slovenia, 2021

One of the main subjects in the field of social networks is to quantify conflict, disagreement, controversy, and polarization, and some quantitative indicators have been developed to quantify these concepts. However, direct computation of these indicators involves the operations of matrix inversion and multiplication, which make it computationally infeasible for large-scale graphs with millions of nodes. In this paper, by reducing the problem of computing relevant quantities to evaluating ℓ2 norms of some vectors, we present a nearly linear time algorithm to estimate all these quantities. Our algorithm is based on the Laplacian solvers, and has a proved theoretical guarantee of error for each quantity. We execute extensive numerical experiments on a variety of real networks, which demonstrate that our approximation algorithm is efficient and effective, scalable to large graphs having millions of nodes.

Recommended citation: Xu Wanyue, Bao Qi, and Zhang Zhongzhi. Fast evaluation for relevant quantities of opinion dynamics. In: Proceedings of the Web Conference (WWW 2021), Ljubljana, Slovenia, April 19-23, 2021, pp.2037-2045. http://vivian1tsui.github.io/files/WWW2021.pdf

Some Combinatorial Problems in Power-Law Graphs

Published in The Computer Journal, 2021

The power-law behavior is ubiquitous in a majority of real-world networks, and it was shown to have a strong effect on various combinatorial, structural and dynamical properties of graphs. For example, it has been shown that in real-life power-law networks, both the matching number and the domination number are relatively smaller, compared with homogeneous graphs. In this paper, we study analytically several combinatorial problems for two power-law graphs with the same number of vertices, edges and the same power exponent. For both graphs, we determine exactly or recursively their matching number, independence number, domination number, the number of maximum matchings, the number of maximum independent sets and the number of minimum dominating sets. We show that power-law behavior itself cannot characterize the combinatorial properties of a heterogenous graph. Since the combinatorial properties studied here have found wide applications in different fields, such as structural controllability of complex networks, our work offers insight in the applications of these combinatorial problems in power-law graphs.

Recommended citation: Jiang Che, Xu Wanyue, Zhou Xiaotian, Zhang Zhongzhi, and Kan Haibin. Some combinatorial problems in power-law graphs. The Computer Journal, 2021. http://vivian1tsui.github.io/files/CompJCombinatorial.pdf

Modeling Higher-Order Interactions in Complex Networks by Edge Product of Graphs

Published in The Computer Journal, 2021

Many graph products have been applied to generate complex networks with striking properties observed in real-world systems. In this paper, we propose a simple generative model for simplicial networks by iteratively using edge corona product. We present a comprehensive analysis of the structural properties of the network model, including degree distribution, diameter, clustering coefficient, as well as distribution of clique sizes, obtaining explicit expressions for these relevant quantities, which agree with the behaviors found in diverse real networks. Moreover, we obtain exact expressions for all the eigenvalues and their associated multiplicities of the normalized Laplacian matrix, based on which we derive explicit formulas for mixing time, mean hitting time and the number of spanning trees. Thus, as previous models generated by other graph products, our model is also an exactly solvable one, whose structural properties can be analytically treated. More interestingly, the expressions for the spectra of our model are also exactly determined, which is sharp contrast to previous models whose spectra can only be given recursively at most. This advantage makes our model a good test bed and an ideal substrate network for studying dynamical processes, especially those closely related to the spectra of normalized Laplacian matrix, in order to uncover the influences of simplicial structure on these processes.

Recommended citation: Wang Yucheng, Yi Yuhao, Xu Wanyue, and Zhang Zhongzhi. Modeling higher-order interactions in complex networks by edge product of graphs. The Computer Journal, 2021. http://vivian1tsui.github.io/files/CompJHigher.pdf

talks

teaching

Teaching experience 1

Undergraduate course, University 1, Department, 2014

This is a description of a teaching experience. You can use markdown like any other post.

Teaching experience 2

Workshop, University 1, Department, 2015

This is a description of a teaching experience. You can use markdown like any other post.