In this paper, considering both cluster heads and sensor nodes, we propose a novel evolving a network model based on a random walk to study the fault tolerance decrease of wireless sensor networks (WSNs) due to node...In this paper, considering both cluster heads and sensor nodes, we propose a novel evolving a network model based on a random walk to study the fault tolerance decrease of wireless sensor networks (WSNs) due to node failure, and discuss the spreading dynamic behavior of viruses in the evolution model. A theoretical analysis shows that the WSN generated by such an evolution model not only has a strong fault tolerance, but also can dynamically balance the energy loss of the entire network. It is also found that although the increase of the density of cluster heads in the network reduces the network efficiency, it can effectively inhibit the spread of viruses. In addition, the heterogeneity of the network improves the network efficiency and enhances the virus prevalence. We confirm all the theoretical results with sufficient numerical simulations.展开更多
In this paper, we study the scaling for the mean first-passage time (MFPT) of the random walks on a generalized Koch network with a trap. Through the network construction, where the initial state is transformed from...In this paper, we study the scaling for the mean first-passage time (MFPT) of the random walks on a generalized Koch network with a trap. Through the network construction, where the initial state is transformed from a triangle to a polygon, we obtain the exact scaling for the MFPT. We show that the MFPT grows linearly with the number of nodes and the dimensions of the polygon in the large limit of the network order. In addition, we determine the exponents of scaling efficiency characterizing the random walks. Our results are the generalizations of those derived for the Koch network, which shed light on the analysis of random walks over various fractal networks.展开更多
Based on the random walk and the intentional random walk, we propose two types of immunization strategies which require only local connectivity information. On several typical scale-free networks, we demonstrate that ...Based on the random walk and the intentional random walk, we propose two types of immunization strategies which require only local connectivity information. On several typical scale-free networks, we demonstrate that these strategies can lead to the eradication of the epidemic by immunizing a small fraction of the nodes in the networks. Particularly, the immunization strategy based on the intentional random walk is extremely efficient for the assortatively mixed networks.展开更多
A novel immunization strategy called the random walk immunization strategy on scale-free networks is proposed. Different from other known immunization strategies, this strategy works as follows: a node is randomly ch...A novel immunization strategy called the random walk immunization strategy on scale-free networks is proposed. Different from other known immunization strategies, this strategy works as follows: a node is randomly chosen from the network. Starting from this node, randomly walk to one of its neighbor node; if the present node is not immunized, then immunize it and continue the random walk; otherwise go back to the previous node and randomly walk again. This process is repeated until a certain fraction of nodes is immunized. By theoretical analysis and numerical simulations, we found that this strategy is very effective in comparison with the other known immunization strategies.展开更多
Unstructured P2P has power-law link distribution, and the random walk in power-law networks is analyzed. The analysis results show that the probability that a random walker walks through the high degree nodes is high ...Unstructured P2P has power-law link distribution, and the random walk in power-law networks is analyzed. The analysis results show that the probability that a random walker walks through the high degree nodes is high in the power-law network, and the information on the high degree nodes can be easily found through random walk. Random walk spread and random walk search method (RWSS) is proposed based on the analysis result. Simulation results show that RWSS achieves high success rates at low cost and is robust to high degree node failure.展开更多
A model is proposed to describe the competition between two kinds of information among N random-walking individuals in an L x L square, starting from a half-and-half mixture of two kinds of information. Individuals re...A model is proposed to describe the competition between two kinds of information among N random-walking individuals in an L x L square, starting from a half-and-half mixture of two kinds of information. Individuals remain or change their information according to their neighbors' information. When the moving speed of individuals v is zero, the two kinds of information typically coexist, and the ratio between them increases with L and decreases with N. In the dynamic case (v 〉 0), only one information eventually remains, and the time required for one information being left scales as Td -v^αL^β^γ.展开更多
基因与表型间的关联分析对揭示生物的内在遗传关联具有重要意义.随机游走算法可以融合多组学数据,聚合一阶或高阶邻居的标签信息,对网络中不同节点间关联信息进行补全,提高关联预测的准确度,进而发现基因和表型间潜在的遗传关联.但现有...基因与表型间的关联分析对揭示生物的内在遗传关联具有重要意义.随机游走算法可以融合多组学数据,聚合一阶或高阶邻居的标签信息,对网络中不同节点间关联信息进行补全,提高关联预测的准确度,进而发现基因和表型间潜在的遗传关联.但现有随机游走算法通常平等地对待每个节点,忽略了不同节点的重要性,使非重要节点过度传播,降低了模型性能.为此,本文提出了一种基于多组学数据融合的个性化随机游走算法(individual Multiple Random Walks,iMRW),在由基因、miRNA及表型节点构建的多组学异质网络上,基于网络拓扑结构,设计个性化多元随机游走策略,为不同重要程度的节点分配不同的游走步长,并结合高斯相互作用属性核相似性与随机游走,对网络不同节点及节点间关联信息进行补全,最终实现多源基因-表型关联矩阵的融合,准确获取基因-表型关联预测矩阵.在不同实验设置下,与主流算法的对比实验结果均显示iMRW能够取得更优的预测性能.在玉米光合作用能力和淀粉含量表型的实验分析结果也进一步证实了iMRW在识别潜在的基因-表型关联的实用性与有效性.展开更多
现有大多数用于识别候选疾病基因的随机游走方法通常优先访问高度连接的基因,而可能与已知疾病有关的不知名或连接性差的基因易被忽略或难以识别.此外,这些方法仅访问单个基因网络或各种基因数据的聚合网络,导致偏差和不完整性.因此,设...现有大多数用于识别候选疾病基因的随机游走方法通常优先访问高度连接的基因,而可能与已知疾病有关的不知名或连接性差的基因易被忽略或难以识别.此外,这些方法仅访问单个基因网络或各种基因数据的聚合网络,导致偏差和不完整性.因此,设计一种能控制随机游走运动方向和整合多种数据源的候选疾病基因识别方法将是一个迫切需要解决的问题.为此,首先构建多层网络和多层异构基因网络.然后,提出一种游走于多层网络和多层异构网络的拓扑偏置重启随机游走(Biased random walk with restart,BRWR)算法来识别疾病基因.实验结果表明,游走于不同类型网络上的识别候选疾病基因的BRWR算法优于现有的算法.最后,应用于多层异构网络上的BRWR算法能预测未诊断的新生儿类早衰综合征中涉及的疾病基因.展开更多
近年来,利用高阶交互信息进行多层网络社区检测已成为复杂网络分析领域的研究热点。尽管多层网络社区检测的研究已取得了一些进展,但大多数方法忽略了网络各层之间的联系。为了解决这一问题,提出了一种模体(motif)感知的自适应跨层游走...近年来,利用高阶交互信息进行多层网络社区检测已成为复杂网络分析领域的研究热点。尽管多层网络社区检测的研究已取得了一些进展,但大多数方法忽略了网络各层之间的联系。为了解决这一问题,提出了一种模体(motif)感知的自适应跨层游走社区检测算法(Motif-aware Adaptive Cross-Layer random walk Community Detection,MACLCD)。该算法充分考虑了多层网络各层内的高阶交互特性以及层间的相关性,有效整合了多层网络的结构信息,提高了社区检测结果的准确性。具体地,首先从网络和节点的角度进行综合度量,揭示网络层间相关性;其次,考虑了各层网络可能具有不同的局部和全局结构特征,利用motif识别各层网络特有的高阶交互结构,构建多层加权混合阶网络;进一步,设计了多层网络跨层游走模型,并引入跳转因子,以确保随机游走能够自适应地遍历多层网络,从而捕获更丰富的网络结构信息。在4个真实的网络数据集上进行实验比较分析,结果表明MACLCD算法在社区检测方面性能较优,相比目前表现最佳的对比算法在ACC和NMI上分别提高了10%和8.9%。展开更多
基金Project supported by the National Natural Science Foundation of China (Grant Nos. 61103231 and 61103230)the Innovation Program of Graduate Scientific Research in Institution of Higher Education of Jiangsu Province, China (Grant No. CXZZ11 0401)
文摘In this paper, considering both cluster heads and sensor nodes, we propose a novel evolving a network model based on a random walk to study the fault tolerance decrease of wireless sensor networks (WSNs) due to node failure, and discuss the spreading dynamic behavior of viruses in the evolution model. A theoretical analysis shows that the WSN generated by such an evolution model not only has a strong fault tolerance, but also can dynamically balance the energy loss of the entire network. It is also found that although the increase of the density of cluster heads in the network reduces the network efficiency, it can effectively inhibit the spread of viruses. In addition, the heterogeneity of the network improves the network efficiency and enhances the virus prevalence. We confirm all the theoretical results with sufficient numerical simulations.
基金Project supported by the Research Foundation of Hangzhou Dianzi University,China (Grant Nos. KYF075610032 andzx100204004-7)the Hong Kong Research Grants Council,China (Grant No. CityU 1114/11E)
文摘In this paper, we study the scaling for the mean first-passage time (MFPT) of the random walks on a generalized Koch network with a trap. Through the network construction, where the initial state is transformed from a triangle to a polygon, we obtain the exact scaling for the MFPT. We show that the MFPT grows linearly with the number of nodes and the dimensions of the polygon in the large limit of the network order. In addition, we determine the exponents of scaling efficiency characterizing the random walks. Our results are the generalizations of those derived for the Koch network, which shed light on the analysis of random walks over various fractal networks.
文摘Based on the random walk and the intentional random walk, we propose two types of immunization strategies which require only local connectivity information. On several typical scale-free networks, we demonstrate that these strategies can lead to the eradication of the epidemic by immunizing a small fraction of the nodes in the networks. Particularly, the immunization strategy based on the intentional random walk is extremely efficient for the assortatively mixed networks.
基金supported by the National Natural Science Foundation of China (No.60774088)the Program for New Century Excellent Talents in University of China (No.NCET-2005-229)the Science and Technology Research Key Project of Education Ministry of China (No.107024)
文摘A novel immunization strategy called the random walk immunization strategy on scale-free networks is proposed. Different from other known immunization strategies, this strategy works as follows: a node is randomly chosen from the network. Starting from this node, randomly walk to one of its neighbor node; if the present node is not immunized, then immunize it and continue the random walk; otherwise go back to the previous node and randomly walk again. This process is repeated until a certain fraction of nodes is immunized. By theoretical analysis and numerical simulations, we found that this strategy is very effective in comparison with the other known immunization strategies.
文摘Unstructured P2P has power-law link distribution, and the random walk in power-law networks is analyzed. The analysis results show that the probability that a random walker walks through the high degree nodes is high in the power-law network, and the information on the high degree nodes can be easily found through random walk. Random walk spread and random walk search method (RWSS) is proposed based on the analysis result. Simulation results show that RWSS achieves high success rates at low cost and is robust to high degree node failure.
基金supported by the National Natural Science Foundation of China (Grant Nos. 61173183, 60973152, and 60573172)the Superior University Doctor Subject Special Scientific Research Foundation of China (Grant No. 20070141014)the Natural Science Foundation of Liaoning Province of China (Grant No. 20082165)
文摘A model is proposed to describe the competition between two kinds of information among N random-walking individuals in an L x L square, starting from a half-and-half mixture of two kinds of information. Individuals remain or change their information according to their neighbors' information. When the moving speed of individuals v is zero, the two kinds of information typically coexist, and the ratio between them increases with L and decreases with N. In the dynamic case (v 〉 0), only one information eventually remains, and the time required for one information being left scales as Td -v^αL^β^γ.
文摘基因与表型间的关联分析对揭示生物的内在遗传关联具有重要意义.随机游走算法可以融合多组学数据,聚合一阶或高阶邻居的标签信息,对网络中不同节点间关联信息进行补全,提高关联预测的准确度,进而发现基因和表型间潜在的遗传关联.但现有随机游走算法通常平等地对待每个节点,忽略了不同节点的重要性,使非重要节点过度传播,降低了模型性能.为此,本文提出了一种基于多组学数据融合的个性化随机游走算法(individual Multiple Random Walks,iMRW),在由基因、miRNA及表型节点构建的多组学异质网络上,基于网络拓扑结构,设计个性化多元随机游走策略,为不同重要程度的节点分配不同的游走步长,并结合高斯相互作用属性核相似性与随机游走,对网络不同节点及节点间关联信息进行补全,最终实现多源基因-表型关联矩阵的融合,准确获取基因-表型关联预测矩阵.在不同实验设置下,与主流算法的对比实验结果均显示iMRW能够取得更优的预测性能.在玉米光合作用能力和淀粉含量表型的实验分析结果也进一步证实了iMRW在识别潜在的基因-表型关联的实用性与有效性.
文摘现有大多数用于识别候选疾病基因的随机游走方法通常优先访问高度连接的基因,而可能与已知疾病有关的不知名或连接性差的基因易被忽略或难以识别.此外,这些方法仅访问单个基因网络或各种基因数据的聚合网络,导致偏差和不完整性.因此,设计一种能控制随机游走运动方向和整合多种数据源的候选疾病基因识别方法将是一个迫切需要解决的问题.为此,首先构建多层网络和多层异构基因网络.然后,提出一种游走于多层网络和多层异构网络的拓扑偏置重启随机游走(Biased random walk with restart,BRWR)算法来识别疾病基因.实验结果表明,游走于不同类型网络上的识别候选疾病基因的BRWR算法优于现有的算法.最后,应用于多层异构网络上的BRWR算法能预测未诊断的新生儿类早衰综合征中涉及的疾病基因.
文摘近年来,利用高阶交互信息进行多层网络社区检测已成为复杂网络分析领域的研究热点。尽管多层网络社区检测的研究已取得了一些进展,但大多数方法忽略了网络各层之间的联系。为了解决这一问题,提出了一种模体(motif)感知的自适应跨层游走社区检测算法(Motif-aware Adaptive Cross-Layer random walk Community Detection,MACLCD)。该算法充分考虑了多层网络各层内的高阶交互特性以及层间的相关性,有效整合了多层网络的结构信息,提高了社区检测结果的准确性。具体地,首先从网络和节点的角度进行综合度量,揭示网络层间相关性;其次,考虑了各层网络可能具有不同的局部和全局结构特征,利用motif识别各层网络特有的高阶交互结构,构建多层加权混合阶网络;进一步,设计了多层网络跨层游走模型,并引入跳转因子,以确保随机游走能够自适应地遍历多层网络,从而捕获更丰富的网络结构信息。在4个真实的网络数据集上进行实验比较分析,结果表明MACLCD算法在社区检测方面性能较优,相比目前表现最佳的对比算法在ACC和NMI上分别提高了10%和8.9%。