The doubly resolving sets are a natural tool to identify where diffusion occurs in a complicated network.Many realworld phenomena,such as rumour spreading on social networks,the spread of infectious diseases,and the s...The doubly resolving sets are a natural tool to identify where diffusion occurs in a complicated network.Many realworld phenomena,such as rumour spreading on social networks,the spread of infectious diseases,and the spread of the virus on the internet,may be modelled using information diffusion in networks.It is obviously impractical to monitor every node due to cost and overhead limits because there are too many nodes in the network,some of which may be unable or unwilling to send information about their state.As a result,the source localization problem is to find the number of nodes in the network that best explains the observed diffusion.This problem can be successfully solved by using its relationship with the well-studied related minimal doubly resolving set problem,which minimizes the number of observers required for accurate detection.This paper aims to investigate the minimal doubly resolving set for certain families of Toeplitz graph Tn(1,t),for t≥2 and n≥t+2.We come to the conclusion that for Tn(1,2),the metric and double metric dimensions are equal and for Tn(1,4),the double metric dimension is exactly one more than the metric dimension.Also,the double metric dimension for Tn(1,3)is equal to the metric dimension for n=5,6,7 and one greater than the metric dimension for n≥8.展开更多
D. Crystal, H. Greenberg, A. Kolem, W. Morris, A. Raian, R. Rardin和 M. Trick指出:从我们对Swart的文章的研究,确信变量公式是正确的,但Swart对关键性引理5.4的证明是错误的。在这里,我们给出引理5.4的一个严格证明,证明引理是完...D. Crystal, H. Greenberg, A. Kolem, W. Morris, A. Raian, R. Rardin和 M. Trick指出:从我们对Swart的文章的研究,确信变量公式是正确的,但Swart对关键性引理5.4的证明是错误的。在这里,我们给出引理5.4的一个严格证明,证明引理是完全正确的,并进一步推广引理5.4的结果。 Swart引理5.4;给定了一个n×n双随机矩阵D,它的所有元素是非负整数,并且每一行和与列和都是正整数K,则D能分解成置换矩阵的线性组合。推论:给定一个n×n双随机矩阵D,它的所有元素是非负整数,并且每一行和与列和都正实数K,则D能分解成置换矩阵的线性组合。展开更多
A necessary and sufficient condition is given for a doubly nonnegative matrix realization of a cycle to be completely positive. Also some special non-CP graphs are investigated.
An n × n real matrix A is called doubly nounegative, if A is entrywise nonnegative and semidefmite positive as well. A is called completely positive if A can be factored as A=BBt,where B is some nonnegative n ...An n × n real matrix A is called doubly nounegative, if A is entrywise nonnegative and semidefmite positive as well. A is called completely positive if A can be factored as A=BBt,where B is some nonnegative n × m matrix. The smallest such number m is called the factorization index (or CP-rank) of A. This paper presents a criteria for a doubly nonnegative matrix realization of a cycle to be completely positive, which is strightforward and effective.展开更多
In this note, we extend the algorithms Extra [13] and subgradient-push [I0] to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stat...In this note, we extend the algorithms Extra [13] and subgradient-push [I0] to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes. We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex. In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.展开更多
文摘The doubly resolving sets are a natural tool to identify where diffusion occurs in a complicated network.Many realworld phenomena,such as rumour spreading on social networks,the spread of infectious diseases,and the spread of the virus on the internet,may be modelled using information diffusion in networks.It is obviously impractical to monitor every node due to cost and overhead limits because there are too many nodes in the network,some of which may be unable or unwilling to send information about their state.As a result,the source localization problem is to find the number of nodes in the network that best explains the observed diffusion.This problem can be successfully solved by using its relationship with the well-studied related minimal doubly resolving set problem,which minimizes the number of observers required for accurate detection.This paper aims to investigate the minimal doubly resolving set for certain families of Toeplitz graph Tn(1,t),for t≥2 and n≥t+2.We come to the conclusion that for Tn(1,2),the metric and double metric dimensions are equal and for Tn(1,4),the double metric dimension is exactly one more than the metric dimension.Also,the double metric dimension for Tn(1,3)is equal to the metric dimension for n=5,6,7 and one greater than the metric dimension for n≥8.
基金Supported by National Natural Science Foundation of China(10971137)National Key Basic Research(973)Program of China(2006CB805900)a grant from Science and Technology Commission of Shanghai Municipality(09XD1402500)
文摘D. Crystal, H. Greenberg, A. Kolem, W. Morris, A. Raian, R. Rardin和 M. Trick指出:从我们对Swart的文章的研究,确信变量公式是正确的,但Swart对关键性引理5.4的证明是错误的。在这里,我们给出引理5.4的一个严格证明,证明引理是完全正确的,并进一步推广引理5.4的结果。 Swart引理5.4;给定了一个n×n双随机矩阵D,它的所有元素是非负整数,并且每一行和与列和都是正整数K,则D能分解成置换矩阵的线性组合。推论:给定一个n×n双随机矩阵D,它的所有元素是非负整数,并且每一行和与列和都正实数K,则D能分解成置换矩阵的线性组合。
基金This research is supported by the Education Committee of Anhui Province.
文摘A necessary and sufficient condition is given for a doubly nonnegative matrix realization of a cycle to be completely positive. Also some special non-CP graphs are investigated.
基金Supported by Anhui Edncation Committee(LJ990007)
文摘An n × n real matrix A is called doubly nounegative, if A is entrywise nonnegative and semidefmite positive as well. A is called completely positive if A can be factored as A=BBt,where B is some nonnegative n × m matrix. The smallest such number m is called the factorization index (or CP-rank) of A. This paper presents a criteria for a doubly nonnegative matrix realization of a cycle to be completely positive, which is strightforward and effective.
文摘In this note, we extend the algorithms Extra [13] and subgradient-push [I0] to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes. We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex. In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.
