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.展开更多
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.展开更多
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.展开更多
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.展开更多
A set in Rd is called regular if its Hausdorff dimension coincides with its upper box counting dimension. It is proved that a random graph-directed self-similar set is regular a.e..
In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability o...In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.展开更多
Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are appro...Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.展开更多
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.展开更多
We consider the earthquake model on a random graph. A detailed analysis of the probability distribution of the size of the avalanches will be given. The model with different inhomogeneities is studied in order to comp...We consider the earthquake model on a random graph. A detailed analysis of the probability distribution of the size of the avalanches will be given. The model with different inhomogeneities is studied in order to compare the critical behavior of different systems. The results indicate that with the increase of the inhomogeneities, the avalanche exponents reduce, i.e., the different numbers of defects cause different critical behaviors of the system. This is virtually ascribed to the dynamical perturbation.展开更多
The origin of power-law distributions in self-organized criticality is investigated by treating the variation of the number of active sites in the system as a stochastic process. An avalanche is then regarded as a fir...The origin of power-law distributions in self-organized criticality is investigated by treating the variation of the number of active sites in the system as a stochastic process. An avalanche is then regarded as a first-return random walk process in a one-dimensional lattice. We assume that the variation of the number of active sites has three possibilities in each update： to increase by 1 with probability f1, to decrease by 1 with probability f2, or remain unchanged with probability 1 - f1 - f2. This mimics the dynamics in the system. Power-law distributions of the lifetime are found when the random walk is unbiased with equal probability to move in opposite directions. This shows that power-law distributions in self-organized criticality may be caused by the balance of competitive interactions.展开更多
A simple stochastic mechanism that produces exact and approximate power-law distributions is presented. The model considers radially symmetric Gaussian, exponential and power-law functions inn= 1, 2, 3 dimensions. Ran...A simple stochastic mechanism that produces exact and approximate power-law distributions is presented. The model considers radially symmetric Gaussian, exponential and power-law functions inn= 1, 2, 3 dimensions. Randomly sampling these functions with a radially uniform sampling scheme produces heavy-tailed distributions. For two-dimensional Gaussians and one-dimensional exponential functions, exact power-laws with exponent –1 are obtained. In other cases, densities with an approximate power-law behaviour close to the origin arise. These densities are analyzed using Padé approximants in order to show the approximate power-law behaviour. If the sampled function itself follows a power-law with exponent –α, random sampling leads to densities that also follow an exact power-law, with exponent -n/a – 1. The presented mechanism shows that power-laws can arise in generic situations different from previously considered specialized systems such as multi-particle systems close to phase transitions, dynamical systems at bifurcation points or systems displaying self-organized criticality. Thus, the presented mechanism may serve as an alternative hypothesis in system identification problems.展开更多
以深度学习框架为基础,提出了一种时空联合供水管网漏损检测模型。该模型首先运用Node2Vec算法求解不同时间段内节点特征;其次,通过模糊C-均值聚类法,利用管网模型节点特征进行分区。最后,以不同时间段的压力敏感度作为输入,漏损位置的...以深度学习框架为基础,提出了一种时空联合供水管网漏损检测模型。该模型首先运用Node2Vec算法求解不同时间段内节点特征;其次,通过模糊C-均值聚类法,利用管网模型节点特征进行分区。最后,以不同时间段的压力敏感度作为输入,漏损位置的分区号作为标签,通过深度信念神经网络进行训练,并通过训练后的模型对管网漏损位置进行检测。在实例分析中,以A市实际供水管网拓扑结构进行验证,利用MATLAB-Open Water Analytics toolbox联合编程建模,结果表明,各个时间段的检测效果均较优,正确率均达到为80%以上。因此,该模型能够有效地检测管网漏损。展开更多
基金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.
基金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.
基金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.
文摘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.
文摘A set in Rd is called regular if its Hausdorff dimension coincides with its upper box counting dimension. It is proved that a random graph-directed self-similar set is regular a.e..
文摘In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.
文摘Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.
基金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.
基金The project supported by National Natural Science Foundation of China under Grant No. 50272022
文摘We consider the earthquake model on a random graph. A detailed analysis of the probability distribution of the size of the avalanches will be given. The model with different inhomogeneities is studied in order to compare the critical behavior of different systems. The results indicate that with the increase of the inhomogeneities, the avalanche exponents reduce, i.e., the different numbers of defects cause different critical behaviors of the system. This is virtually ascribed to the dynamical perturbation.
基金The project supported in part by National Natural Science Foundation of China under Grant Nos.10635020 and 10475032the Major Project of the Ministry of Education of China under Grant No.306022.
文摘The origin of power-law distributions in self-organized criticality is investigated by treating the variation of the number of active sites in the system as a stochastic process. An avalanche is then regarded as a first-return random walk process in a one-dimensional lattice. We assume that the variation of the number of active sites has three possibilities in each update： to increase by 1 with probability f1, to decrease by 1 with probability f2, or remain unchanged with probability 1 - f1 - f2. This mimics the dynamics in the system. Power-law distributions of the lifetime are found when the random walk is unbiased with equal probability to move in opposite directions. This shows that power-law distributions in self-organized criticality may be caused by the balance of competitive interactions.
文摘A simple stochastic mechanism that produces exact and approximate power-law distributions is presented. The model considers radially symmetric Gaussian, exponential and power-law functions inn= 1, 2, 3 dimensions. Randomly sampling these functions with a radially uniform sampling scheme produces heavy-tailed distributions. For two-dimensional Gaussians and one-dimensional exponential functions, exact power-laws with exponent –1 are obtained. In other cases, densities with an approximate power-law behaviour close to the origin arise. These densities are analyzed using Padé approximants in order to show the approximate power-law behaviour. If the sampled function itself follows a power-law with exponent –α, random sampling leads to densities that also follow an exact power-law, with exponent -n/a – 1. The presented mechanism shows that power-laws can arise in generic situations different from previously considered specialized systems such as multi-particle systems close to phase transitions, dynamical systems at bifurcation points or systems displaying self-organized criticality. Thus, the presented mechanism may serve as an alternative hypothesis in system identification problems.
文摘以深度学习框架为基础,提出了一种时空联合供水管网漏损检测模型。该模型首先运用Node2Vec算法求解不同时间段内节点特征;其次,通过模糊C-均值聚类法,利用管网模型节点特征进行分区。最后,以不同时间段的压力敏感度作为输入,漏损位置的分区号作为标签,通过深度信念神经网络进行训练,并通过训练后的模型对管网漏损位置进行检测。在实例分析中,以A市实际供水管网拓扑结构进行验证,利用MATLAB-Open Water Analytics toolbox联合编程建模,结果表明,各个时间段的检测效果均较优,正确率均达到为80%以上。因此,该模型能够有效地检测管网漏损。
