A novel configuration model for random graphs with given degree sequence

Recently, random graphs in which vertices are characterized by hidden variables controlling the establishment of edges between pairs of vertices have attracted much attention. This paper presents a specific realization of a class of random network models in which the connection probability between two vertices （i, j） is a specific function of degrees ki and kj. In the framework of the configuration model of random graphsp we find the analytical expressions for the degree correlation and clustering as a function of the variance of the desired degree distribution. The obtained expressions are checked by means of numerical simulations. Possible applications of our model are discussed.

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

Rainbow and Monochromatic Vertex-connection of Random Graphs

A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-connection number rvc(G)is the minimum number of colors used such that there is a rainbow path joining any two vertices of G;whereas the monochromatic vertex-connection number mvc(G)is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path.These two opposite concepts are the vertex-versions of rainbow connection number rc(G)and monochromatic connection number mc(G)respectively.The study on rc(G)and mc(G)of random graphs drew much attention,and there are few results on the rainbow and monochromatic vertex-connection numbers.In this paper,we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them,respectively.

Number of edges in inhomogeneous random graphs

We study the number of edges in the inhomogeneous random graph when vertex weights have an infinite mean and show that the number of edges is O(n log n).Central limit theorems for the number of edges are also established.

Large Deviations in Generalized Random Graphs with Node Weights

Generalized random graphs are considered where the presence or absence of an edge de- pends on the weights of its nodes. Our main interest is to investigate large deviations for the number of edges per node in such a generalized random graph, where the node weights are deterministic under some regularity conditions, as well as chosen i.i.d, from a finite set with positive components. When the node weights are random variables, obstacles arise because the independence among edges no longer exists, our main tools are some results of large deviations for mixtures. After calculating, our results show that the corresponding rate functions for the deterministic case and the random case are very different.

Dual-stage constructed random graph algorithm to generate random graphs featuring the same topological characteristics with power grids

It is a common practice to simulate some historical or test systems to validate the efficiency of new methods or concepts. However, there are only a small number of existing power system test cases, and validation and evaluation results, obtained using such a limited number of test cases, may not be deemed sufficient or convincing. In order to provide more available test cases, a new random graph generation algorithm, named ‘‘dualstage constructed random graph’’ algorithm, is proposed to effectively model the power grid topology. The algorithm generates a spanning tree to guarantee the connectivity of random graphs and is capable of controlling the number of lines precisely. No matter how much the average degree is,whether sparse or not, random graphs can be quickly formed to satisfy the requirements. An approach is developed to generate random graphs with prescribed numbers of connected components, in order to simulate the power grid topology under fault conditions. Our experimental study on several realistic power grid topologies proves that the proposed algorithm can quickly generate a large number of random graphs with the topology characteristics of real-world power grid.

Convergence of Distributed Gradient-Tracking-Based Optimization Algorithms with Random Graphs

This paper studies distributed convex optimization over a multi-agent system,where each agent owns only a local cost function with convexity and Lipschitz continuous gradients.The goal of the agents is to cooperatively minimize a sum of the local cost functions.The underlying communication networks are modelled by a sequence of random and balanced digraphs,which are not required to be spatially or temporally independent and have any special distributions.The authors use a distributed gradient-tracking-based optimization algorithm to solve the optimization problem.In the algorithm,each agent makes an estimate of the optimal solution and an estimate of the average of all the local gradients.The values of the estimates are updated based on a combination of a consensus method and a gradient tracking method.The authors prove that the algorithm can achieve convergence to the optimal solution at a geometric rate if the conditional graphs are uniformly strongly connected,the global cost function is strongly convex and the step-sizes don’t exceed some upper bounds.

A Note on the Existence of Fractional f-factors in Random Graphs

Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.

Markov Chains Based on Random Generalized 1-Flipper Operations for Connected Regular Multi-digraphs

The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-Flipper operation preserves the regularity and weak connectivity of multi-digraphs.The generalized 1-Flipper operation is proved to be symmetric.Moreover,it is presented that a series of random generalized 1-Flipper operations eventually lead to a uniform probability distribution over all connected d-regular multi-digraphs without loops.

THE STATIONARY DISTRIBUTION OF A CONTINUOUS－TIME RANDOM GRAPH PROCESS WITH INTERACTING EDGES

In previous papers, the stationary distributions of a class of discrete and continuoustime random graph processes with state space consisting of the simple and directed graphs on Nvenices were studied. In this paper, the random graph graph process is extended one impotent stepfurther by allowing interaction of edges. Similarly, We obtha the expressions of the stationarydistributions and prove that the process is ergodic under different editions.

Interpreting Randomly Wired Graph Models for Chinese NER

Interpreting deep neural networks is of great importance to understand and verify deep models for natural language processing(NLP)tasks.However,most existing approaches only focus on improving the performance of models but ignore their interpretability.In this work,we propose a Randomly Wired Graph Neural Network(RWGNN)by using graph to model the structure of Neural Network,which could solve two major problems(word-boundary ambiguity and polysemy)of ChineseNER.Besides,we develop a pipeline to explain the RWGNNby using Saliency Map and Adversarial Attacks.Experimental results demonstrate that our approach can identify meaningful and reasonable interpretations for hidden states of RWGNN.

Average flooding distance for MANETs in random graph models with spatial reuse

The flooding distance is an important parameter in the design and evaluation of a routing protocol, which is related not only to the delay time in the route discovery, but also to the stability and reliability of the route. In this paper, the average flooding distance （AFD） for a mobile ad hoc network （MANET） in a random graph model was given based on the dynamic source routing （DSR） protocol. The influence of spatial reuse on the AFD was also studied. Compared with that in the model without the spatial reuse, the AFD in the model with the spatial reuse has much smaller value, when the connetivity probability between nodes in the network is small and when the number of reused times is large. This means that the route discovery with the spatial reuse is much more effective.

Evolution, resilience and causes of global petroleum gas trade networks: 1995-2020

Based on the HS 4-digit code trade data in UNCOMTRADE from 1995 to 2020, this paper analyzes the characteristics of the evolution of the global PG trade network using the complex network approach and analyzes the changes in its resilience at the overall and country levels, respectively. The results illustrated that:(1) The scale of the global PG trade network tends to expand, and the connection is gradually tightened, experiencing a change from a “supply-oriented” to a “supply-and-demand” pattern, in which the U.S., Russia, Qatar, and Australia have gradually replaced Canada, Japan, and Russia to become the core trade status, while OPEC countries such as Qatar, Algeria, and Kuwait mainly rely on PG exports to occupy the core of the global supply, and the trade status of other countries has been dynamically alternating and evolving.(2) The resilience of the global PG trade network is lower than that of the random network and decreases non-linearly with more disrupted countries. Moreover, the impact of the U.S. is more significant than the rest of countries. Simulations using the exponential random graph model(ERGM) model revealed that national GDP, institutional quality, common border and RTA network are the determinants of PG trade network formation, and the positive impact of the four factors not only varies significantly across regions and stages, but also increases with national network status.

Efficient unequal error protection for online fountain codes

In this paper,an efficient unequal error protection(UEP)scheme for online fountain codes is proposed.In the buildup phase,the traversing-selection strategy is proposed to select the most important symbols(MIS).Then,in the completion phase,the weighted-selection strategy is applied to provide low overhead.The performance of the proposed scheme is analyzed and compared with the existing UEP online fountain scheme.Simulation results show that in terms of MIS and the least important symbols(LIS),when the bit error ratio is 10-4,the proposed scheme can achieve 85%and 31.58%overhead reduction,respectively.

A Robustness Model of Complex Networks with Tunable Attack Information Parameter

We introduce a novel model for robustness of complex with a tunable attack information parameter. The random failure and intentional attack known are the two extreme cases of our model. Based on the model, we study the robustness of complex networks under random information and preferential information, respectively. Using the generating function method, we derive the exact value of the critical removal fraction of nodes for the disintegration of networks and the size of the giant component. We show that hiding just a small fraction of nodes randomly can prevent a scale-free network from collapsing and detecting just a small fraction of nodes preferentially can destroy a scale-free network.

The effects of degree correlations on network topologies and robustness

Complex networks have been applied to model numerous interactive nonlinear systems in the real world. Knowledge about network topology is crucial to an understanding of the function, performance and evolution of complex systems. In the last few years, many network metrics and models have been proposed to investigate the network topology, dynamics and evolution. Since these network metrics and models are derived from a wide range of studies, a systematic study is required to investigate the correlations among them. The present paper explores the effect of degree correlation on the other network metrics through studying an ensemble of graphs where the degree sequence （set of degrees） is fixed. We show that to some extent, the characteristic path length, clustering coefficient, modular extent and robustness of networks are directly influenced by the degree correlation.

Joint probability generating function for degrees of active/passive random intersection graphs

Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability generating function for degrees of GactVe（n, re, p） and GPaSSiW（n, re, p）, which are generated by a random bipartite graph G＊ （n, ~rt, p） on n ＋ rn vertices.

Rainbow k-connectivity of Random Bipartite Graphs

A path in an edge-colored graph G is called a rainbow path if no two edges of the path are colored the same color.The minimum number of colors required to color the edges of G such that every pair of vertices are connec ted by at least k internally ver tex-disjoint rainbow paths is called the rainbow k-connectivity of the graph G,denoted by rck(G).For the random graph G(n,p),He and Liang got a sharp threshold function for the property rck(G(n,p))≤d.For the random equi-bipartite graph G(n,n,p),Fujita et.al.got a sharp threshold function for the property rck(G(n,n,p))≤3.They also posed the following problem:For d≥2,determine a sharp threshold function for the property rck(G)≤d,where G is another random graph model.This paper is to give a solution to their problem in the general random bipartite graph model G(m,n,p).

Finite family trees of continuous time birth and death processes for evaluating the transmitting speed of information on communication networks

A finite random graph generated by continuous time birth and death processes with exponentially distributed waiting times was investigated, which is similar to a communication network in daily life. The vertices are the living particles, and directed edges go from mothers to daughters. The size of the communication network was studied. Furthermore, the probability of successfully connecting senders with receivers and the transmitting speed of information were obtained.

Some Properties for the Largest Component of Random Geometric Graphs with Applications in Sensor Networks

In this paper we consider the standard Poisson Boolean model of random geometric graphs G（Hλ,s; 1） in Rd and study the properties of the order of the largest component L1 （G（Hλ,s; 1）） . We prove that ElL1 （G（Hλ,s; 1））] is smooth with respect to A, and is derivable with respect to s. Also, we give the expression of these derivatives. These studies provide some new methods for the theory of the largest component of finite random geometric graphs （not asymptotic graphs as s - co） in the high dimensional space （d 〉 2）. Moreover, we investigate the convergence rate of E[L1（G（Hλ,s; 1））]. These results have significance for theory development of random geometric graphs and its practical application. Using our theories, we construct and solve a new optimal energy-efficient topology control model of wireless sensor networks, which has the significance of theoretical foundation and guidance for the design of network layout.