Background： The frequency of small subtrees in biological, social, and other types of networks could shed light into the structure, function, and evolution of such networks. However, counting all possible subtrees of...Background： The frequency of small subtrees in biological, social, and other types of networks could shed light into the structure, function, and evolution of such networks. However, counting all possible subtrees of a prescribed size can be computationally expensive because of their potentially large number even in small, sparse networks. Moreover, most of the existing algorithms for subtree counting belong to the subtree-centric approaches, which search for a specific single subtree type at a time, potentially taking more time by searching again on the same network. Methods： In this paper, we propose a network-centric algorithm （MTMO） to efficiently count k-size subtrees. Our algorithm is based on the enumeration of all connected sets of k-1 edges, incorporates a labeled rooted tree data structure in the enumeration process to reduce the number of isomorphism tests required, and uses an array-based indexing scheme to simplify the subtree counting method. Results： The experiments on three representative undirected complex networks show that our algorithm is roughly an order of magnitude faster than existing subtree-centric approaches and base network-centric algorithm which does not use rooted tree, allowing for counting larger subtrees in larger networks than previously possible. We also show major differences between unicellular and multicellular organisms. In addition, our algorithm is applied to find network motifs based on pattern growth approach. Conclusions： A network-centric algorithm which allows for a This enables us to count larger motif in larger networks than faster counting of non-induced subtrees is proposed previously.展开更多
Many real-world networks have the ability to adapt themselves in response to the state of their nodes. This paper studies controlling disease spread on network with feedback mechanism, where the susceptible nodes are ...Many real-world networks have the ability to adapt themselves in response to the state of their nodes. This paper studies controlling disease spread on network with feedback mechanism, where the susceptible nodes are able to avoid contact with the infected ones by cutting their connections with probability when the density of infected nodes reaches a certain value in the network. Such feedback mechanism considers the networks＇ own adaptivity and the cost of immunization. The dynamical equations about immunization with feedback mechanism ave solved and theoretical predictions are in agreement with the results of large scale simulations. It shows that when the lethality a increases, the prevalence decreases more greatly with the same immunization g. That is, with the same cost, a better controlling result can be obtained. This approach offers an effective and practical policy to control disease spread, and also may be relevant to other similar networks.展开更多
基金This work was supported by the National Natural Science Foundation of China （No. 61572180） and Scientific and Technological Research Project of Education Department in Jiangxi Province （No. GJJ170383）,
文摘Background： The frequency of small subtrees in biological, social, and other types of networks could shed light into the structure, function, and evolution of such networks. However, counting all possible subtrees of a prescribed size can be computationally expensive because of their potentially large number even in small, sparse networks. Moreover, most of the existing algorithms for subtree counting belong to the subtree-centric approaches, which search for a specific single subtree type at a time, potentially taking more time by searching again on the same network. Methods： In this paper, we propose a network-centric algorithm （MTMO） to efficiently count k-size subtrees. Our algorithm is based on the enumeration of all connected sets of k-1 edges, incorporates a labeled rooted tree data structure in the enumeration process to reduce the number of isomorphism tests required, and uses an array-based indexing scheme to simplify the subtree counting method. Results： The experiments on three representative undirected complex networks show that our algorithm is roughly an order of magnitude faster than existing subtree-centric approaches and base network-centric algorithm which does not use rooted tree, allowing for counting larger subtrees in larger networks than previously possible. We also show major differences between unicellular and multicellular organisms. In addition, our algorithm is applied to find network motifs based on pattern growth approach. Conclusions： A network-centric algorithm which allows for a This enables us to count larger motif in larger networks than faster counting of non-induced subtrees is proposed previously.
基金Project supported by the National Natural Science Foundation of China （Grant No 10375022）.
文摘Many real-world networks have the ability to adapt themselves in response to the state of their nodes. This paper studies controlling disease spread on network with feedback mechanism, where the susceptible nodes are able to avoid contact with the infected ones by cutting their connections with probability when the density of infected nodes reaches a certain value in the network. Such feedback mechanism considers the networks＇ own adaptivity and the cost of immunization. The dynamical equations about immunization with feedback mechanism ave solved and theoretical predictions are in agreement with the results of large scale simulations. It shows that when the lethality a increases, the prevalence decreases more greatly with the same immunization g. That is, with the same cost, a better controlling result can be obtained. This approach offers an effective and practical policy to control disease spread, and also may be relevant to other similar networks.
