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 realizatio...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.展开更多
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 ther...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.展开更多
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 establis...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.展开更多
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-conne...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.展开更多
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 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.展开更多
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 cooperativel...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.展开更多
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...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.展开更多
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 ...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.展开更多
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-F...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 global clustering of inventive talent shapes innovation capacity and drives economic growth.For China,this process is especially crucial in sustaining its development momentum.This paper draws on data from the EPO...The global clustering of inventive talent shapes innovation capacity and drives economic growth.For China,this process is especially crucial in sustaining its development momentum.This paper draws on data from the EPO Worldwide Patent Statistical Database(PATSTAT)to extract global inventive talent mobility information and analyzes the spatial structural evolution of the global inventive talent flow network.The study finds that this network is undergoing a multi-polar transformation,characterized by the rising importance of a few central countries-such as the United States,Germany,and China-and the increasing marginalization of many peripheral countries.In response to this typical phenomenon,the paper constructs an endogenous migration model and conducts empirical testing using the Temporal Exponential Random Graph Model(TERGM).The results reveal several endogenous mechanisms driving global inventive talent flows,including reciprocity,path dependence,convergence effects,transitivity,and cyclic structures,all of which contribute to the network’s multi-polar trend.In addition,differences in regional industrial structures significantly influence talent mobility choices and are a decisive factor in the formation of poles within the multi-polar landscape.Based on these findings,it is suggested that efforts be made to foster two-way channels for talent exchange between China and other global innovation hubs,in order to enhance international collaboration and knowledge flow.We should aim to reduce the migration costs and institutional barriers faced by R&D personnel,thereby encouraging greater mobility of high-skilled talent.Furthermore,the government is advised to strategically leverage regional strengths in high-tech industries as a lever to capture competitive advantages in emerging technologies and products,ultimately strengthening the country’s position in the global innovation landscape.展开更多
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, ...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 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 model...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.展开更多
We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference ...We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By construct- ing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper.展开更多
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 ...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.展开更多
Exponential random graph models(ERGMs) are flexible probability models allowing edge dependency.However,it is known that to a first-order approximation,many ERGMs behave like Erd?sRényi random graphs,where edges ...Exponential random graph models(ERGMs) are flexible probability models allowing edge dependency.However,it is known that to a first-order approximation,many ERGMs behave like Erd?sRényi random graphs,where edges are independent.In this paper,to distinguish ERGMs from Erd?s-Rényi random graphs,we consider second-order approximations of ERGMs using two-stars and triangles.We prove that the second-order approximation indeed achieves second-order accuracy in the triangle-free case.The new approximation is formally obtained by the Hoeffding decomposition and rigorously justified using Stein's method.展开更多
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 chan...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.展开更多
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...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.展开更多
Let G be a graph and(V_(i),V_(2),...,V_(e))be a k-partition of G.For 1≤i<j≤k,the ratio of(V_(i),V_(j)),denoted by R(V_(i),V_(j)),is e(V_(i),V_(j))/(|V_(i)||V_(j)|),where e(V_(i),V_(j))is the number of crossing ed...Let G be a graph and(V_(i),V_(2),...,V_(e))be a k-partition of G.For 1≤i<j≤k,the ratio of(V_(i),V_(j)),denoted by R(V_(i),V_(j)),is e(V_(i),V_(j))/(|V_(i)||V_(j)|),where e(V_(i),V_(j))is the number of crossing edges.The minimum k-ratio of G,denoted by R_(k)(G),is the minimumΣ_(i)≤i≤k R(V_(i),V_(j))overall k-partions(V_(1),V_(2),..V_(k))of G.Let R(G)=R_(2)(G).The ratio cut problem,posed by Wei and Cheng,and independently by Leighton and Rao,is an extension of the min-cut problem and has important applications in CAD.It is easy to see that Rk(G)is closely related to the density d(G)of a graph G.In this paper,we mainly give some results on Rk(G)with respect to d(G).First,we show that R_(k)(G)≤(2^(K))(1+o(1)d(G)for graphs G and Rk(G)≤(k-1)(1+o(1)d(G)for sparse graphs G.Then,we give some upper and lower bounds on R(G).In particular,we show R(G)≤4/(n-3)for every planar graph G with n≥4 vertices.At last,we consider the random graph G(n,p)and show that R(G(n,p))can be determined asymptotically almost surely if p≥C log n/n for some constant C>0.展开更多
Let{Xi,i∈J}be a family of locally dependent non-negative integer-valued random variables with finite expectations and variances.We consider the sum W=∑_(i∈J)X_(i)and apply Stein's method to establish general up...Let{Xi,i∈J}be a family of locally dependent non-negative integer-valued random variables with finite expectations and variances.We consider the sum W=∑_(i∈J)X_(i)and apply Stein's method to establish general upper error bounds for the total variation distance dTV(W,M),where M represents a threeparameter random variable.As a direct consequence,we obtain a discretized normal approximation for W.As applications,we study four well-known examples in detail:counting vertices where all edges point inward,the birthday problem,counting monochromatic edges in uniformly colored graphs,and triangles in the Erdos-Rényi random graph.Through delicate analysis and computation,we obtain sharper upper error bounds than existing results.展开更多
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 th...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.展开更多
基金Project supported by the National Natural Science Foundation of China （Grant Nos 10375025 and 10275027） and the Cultivation Fund of the Key Scientific and Technical Innovation Project, Ministry of Education of China （Grant No 704035）
文摘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.
文摘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.
基金supported by National Natural Science Foundation of China(Grant No.11671373)。
文摘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.
基金supported by the National Natural Science Foundation of China(Nos.11901196)Natural Science Foundation of Anhui Province(Nos.JZ2020AKZR0295)by the Scholarship Promotion Program of Hefei University of Technology(Nos.JZ2019HGTA0038)。
文摘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.
基金Supported by National Natural Science Foundation of China(Grant Nos.11371169 and 11671168)
文摘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.
基金supported by the Basic Research Project of Shanghai Science and Technology Commission under Grant No.20JC1414000。
文摘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.
文摘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.
基金Supported by NSFSD(No.ZR2013AM001)NSFC(No.11001055),NSFC11371355
文摘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.
基金National Natural Science Foundation of China(No.11671258)。
文摘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.
基金supported by the Major Project of the National Social Science Fund of China,titled“Design Path Selection for the Mechanism of New and Old Growth Driver Conversion”(Grant No.18ZDA077)by the Joint Special Major Research Project of the Yangtze River Delta Economics and Social Development Research Center at Nanjing University and the Collaborative Innovation Center for China Economy(CICCE),titled“Practicing Innovation in China’s Development Economics for the Yangtze River Delta:From Industrial Clusters to Technological Clusters”(Grant No.CYD2022006).
文摘The global clustering of inventive talent shapes innovation capacity and drives economic growth.For China,this process is especially crucial in sustaining its development momentum.This paper draws on data from the EPO Worldwide Patent Statistical Database(PATSTAT)to extract global inventive talent mobility information and analyzes the spatial structural evolution of the global inventive talent flow network.The study finds that this network is undergoing a multi-polar transformation,characterized by the rising importance of a few central countries-such as the United States,Germany,and China-and the increasing marginalization of many peripheral countries.In response to this typical phenomenon,the paper constructs an endogenous migration model and conducts empirical testing using the Temporal Exponential Random Graph Model(TERGM).The results reveal several endogenous mechanisms driving global inventive talent flows,including reciprocity,path dependence,convergence effects,transitivity,and cyclic structures,all of which contribute to the network’s multi-polar trend.In addition,differences in regional industrial structures significantly influence talent mobility choices and are a decisive factor in the formation of poles within the multi-polar landscape.Based on these findings,it is suggested that efforts be made to foster two-way channels for talent exchange between China and other global innovation hubs,in order to enhance international collaboration and knowledge flow.We should aim to reduce the migration costs and institutional barriers faced by R&D personnel,thereby encouraging greater mobility of high-skilled talent.Furthermore,the government is advised to strategically leverage regional strengths in high-tech industries as a lever to capture competitive advantages in emerging technologies and products,ultimately strengthening the country’s position in the global innovation landscape.
文摘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.
基金supported by the National Science Foundation of China(NSFC)underGrants 61876217 and 62176175the Innovative Team of Jiangsu Province under Grant XYDXX-086Jiangsu Postgraduate Research and Innovation Plan(KYCX20_2762).
文摘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.
基金Supported by the National Natural Science Foundation of China (10571139)
文摘We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By construct- ing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper.
基金supported by the National Natural Science Foundation of China（Grant No.60572126）
文摘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.
基金supported by the National Social Science Fund of China (Grant No.20CTQ005)supported by Hong Kong Research Grants Council General Research Fund (Grant Nos.14305821,14304822 and 14303423)a direct grant from the Chinese University of Hong Kong。
文摘Exponential random graph models(ERGMs) are flexible probability models allowing edge dependency.However,it is known that to a first-order approximation,many ERGMs behave like Erd?sRényi random graphs,where edges are independent.In this paper,to distinguish ERGMs from Erd?s-Rényi random graphs,we consider second-order approximations of ERGMs using two-stars and triangles.We prove that the second-order approximation indeed achieves second-order accuracy in the triangle-free case.The new approximation is formally obtained by the Hoeffding decomposition and rigorously justified using Stein's method.
基金funded by the National Natural Science Foundation of China Projects (Grant number 71703128)Anhui Provincial Higher Education Research Key Project (grant number: 2024AH052139)。
文摘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.
基金supported by the National Natural Science Foundation of China(61601147)the Beijing Natural Science Foundation(L182032)。
文摘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.
基金supported by the National Natural Science Foundation of China(No.12071077)a project of Center for Applied Mathematics of Fujian Province,and a cooperation project of HUAWEI.
文摘Let G be a graph and(V_(i),V_(2),...,V_(e))be a k-partition of G.For 1≤i<j≤k,the ratio of(V_(i),V_(j)),denoted by R(V_(i),V_(j)),is e(V_(i),V_(j))/(|V_(i)||V_(j)|),where e(V_(i),V_(j))is the number of crossing edges.The minimum k-ratio of G,denoted by R_(k)(G),is the minimumΣ_(i)≤i≤k R(V_(i),V_(j))overall k-partions(V_(1),V_(2),..V_(k))of G.Let R(G)=R_(2)(G).The ratio cut problem,posed by Wei and Cheng,and independently by Leighton and Rao,is an extension of the min-cut problem and has important applications in CAD.It is easy to see that Rk(G)is closely related to the density d(G)of a graph G.In this paper,we mainly give some results on Rk(G)with respect to d(G).First,we show that R_(k)(G)≤(2^(K))(1+o(1)d(G)for graphs G and Rk(G)≤(k-1)(1+o(1)d(G)for sparse graphs G.Then,we give some upper and lower bounds on R(G).In particular,we show R(G)≤4/(n-3)for every planar graph G with n≥4 vertices.At last,we consider the random graph G(n,p)and show that R(G(n,p))can be determined asymptotically almost surely if p≥C log n/n for some constant C>0.
基金supported by National Natural Science Foundation of China(Grant Nos.12271475 and U23A2064)。
文摘Let{Xi,i∈J}be a family of locally dependent non-negative integer-valued random variables with finite expectations and variances.We consider the sum W=∑_(i∈J)X_(i)and apply Stein's method to establish general upper error bounds for the total variation distance dTV(W,M),where M represents a threeparameter random variable.As a direct consequence,we obtain a discretized normal approximation for W.As applications,we study four well-known examples in detail:counting vertices where all edges point inward,the birthday problem,counting monochromatic edges in uniformly colored graphs,and triangles in the Erdos-Rényi random graph.Through delicate analysis and computation,we obtain sharper upper error bounds than existing results.
基金Supported by the National Natural Science Foundation of China under Grant No 70501032.
文摘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.
