摘要(英) |
The network growth model is designed as a problem of finding the minimal
wiring cost while achieving maximal connections. By mapping to Ising spin
models, two kinds of models were investigated and they show different phase
transition behaviors for different wiring weight distributions and node weight
distributions. Previously, the network properties of undirected network have
been investigated. In this research, we focus on the network properties of our
optimized directed network, such as cluster coefficients, in and out degree dis-
tributions, minimal path length and so on. Based on the mean-field theory, an-
alytical results are also derived. These optimized network properties are sim-
ulated by the efficient algorithm which was developed in our previous work
and fit well with the analytical results. For some specific edge weight and node
weight distributions, the growth of optimized networks behave like scale-free
networks, which are found in many networks in biological system and social
networks. Besides, motifs (sub-graphs) are measured in the optimized network,
which help us to gain insight on the structure of networks. |
參考文獻 |
[1] M. E. J. Newman. “The Structure and Function of Complex Networks”. In: SIAM Review 45.2 (2003), pp. 167–256. DOI: 10 . 1137 /
S003614450342480. eprint: https : / / doi . org / 10 . 1137 /
S003614450342480. URL: https : / / doi . org / 10 . 1137 /
S003614450342480.
[2] Song Yang. Networks: An Introduction by MEJ Newman: Oxford, UK: Oxford
University Press. 720 pp., $85.00. 2013.
[3] Réka Albert and Albert-László Barabási. “Statistical mechanics of complex
networks”. In: Reviews of modern physics 74.1 (2002), p. 47.
[4] Stanley Milgram. “The small world problem”. In: Psychology today 2.1
(1967), pp. 60–67.
[5] Duncan J. Watts and Steven H. Strogatz. “Collective dynamics of ‘smallworld’ networks”. In: Nature 393.6684 (1998), pp. 440–442. DOI: 10.1038/
30918.
[6] Derek J De Solla Price. “Networks of scientific papers: The pattern of bibliographic references indicates the nature of the scientific research front.”
In: Science 149.3683 (1965), pp. 510–515.
[7] Albert-László Barabási and Réka Albert. “Emergence of scaling in random
networks”. In: science 286.5439 (1999), pp. 509–512.
[8] Emily S. C. Ching, Pik-Yin Lai, and C. Y. Leung. “Extracting connectivity from dynamics of networks with uniform bidirectional coupling”. In:
Phys. Rev. E 88 (4 Oct. 2013), p. 042817. DOI: 10.1103/PhysRevE.88.
042817. URL: https://link.aps.org/doi/10.1103/PhysRevE.
88.042817.
[9] Emily SC Ching, Pik-Yin Lai, and CY Leung. “Reconstructing weighted
networks from dynamics”. In: Physical Review E 91.3 (2015), p. 030801.
[10] Zhaoyang Zhang et al. “Solving the inverse problem of noise-driven dynamic networks”. In: Phys. Rev. E 91 (1 Jan. 2015), p. 012814. DOI: 10 .
1103/PhysRevE.91.012814. URL: https://link.aps.org/doi/
10.1103/PhysRevE.91.012814.
[11] Emily SC Ching and HC Tam. “Reconstructing links in directed networks
from noisy dynamics”. In: Physical Review E 95.1 (2017), p. 010301.
88
[12] Pik-Yin Lai. “Reconstructing network topology and coupling strengths in
directed networks of discrete-time dynamics”. In: Phys. Rev. E 95 (2 Feb.
2017), p. 022311. DOI: 10.1103/PhysRevE.95.022311. URL: https:
//link.aps.org/doi/10.1103/PhysRevE.95.022311.
[13] Mark EJ Newman. “Network structure from rich but noisy data”. In: Nature Physics 14.6 (2018), pp. 542–545.
[14] Tiago P. Peixoto and Stefan Bornholdt. “Evolution of Robust Network
Topologies: Emergence of Central Backbones”. In: Phys. Rev. Lett. 109 (11
Sept. 2012), p. 118703. DOI: 10.1103/PhysRevLett.109.118703. URL:
https : / / link . aps . org / doi / 10 . 1103 / PhysRevLett . 109 .
118703.
[15] Bo Li and K. Y. Michael Wong. “Optimizing synchronization stability of
the Kuramoto model in complex networks and power grids”. In: Phys. Rev.
E 95 (1 Jan. 2017), p. 012207. DOI: 10.1103/PhysRevE.95.012207. URL:
https://link.aps.org/doi/10.1103/PhysRevE.95.012207.
[16] Gergely Palla et al. “Statistical mechanics of topological phase transitions
in networks”. In: Physical Review E 69.4 (2004), p. 046117.
[17] Stefan Thurner and Christoly Biely. “Two statistical mechanics aspects of
complex networks”. In: Physica A: Statistical Mechanics and its Applications
372.2 (2006), pp. 346–353.
[18] Ed Bullmore and Olaf Sporns. “The economy of brain network organization”. In: Nature reviews neuroscience 13.5 (2012), pp. 336–349.
[19] , Aleksandra M. Walczak, and William Bialek. “Optimizing information
flow in small genetic networks”. In: Phys. Rev. E 80 (3 Sept. 2009), p. 031920.
DOI: 10.1103/PhysRevE.80.031920. URL: https://link.aps.
org/doi/10.1103/PhysRevE.80.031920.
[20] Aleksandra M. Walczak, and William Bialek. “Optimizing information
flow in small genetic networks. II. Feed-forward interactions”. In: Phys.
Rev. E 81 (4 Apr. 2010), p. 041905. DOI: 10.1103/PhysRevE.81.041905.
URL: https : / / link . aps . org / doi / 10 . 1103 / PhysRevE . 81 .
041905.
[21] Ron Milo et al. “Network motifs: simple building blocks of complex networks”. In: Science 298.5594 (4 Apr. 2002), pp. 824–827. DOI: 10.1103/
PhysRevE.81.041905. URL: https://link.aps.org/doi/10.
1103/PhysRevE.81.041905.
[22] Nadav Kashtan et al. “Topological generalizations of network motifs”. In:
Physical Review E 70.3 (4 Apr. 2004), p. 031909. DOI: 10.1103/PhysRevE.
81 . 041905. URL: https : / / link . aps . org / doi / 10 . 1103 /
PhysRevE.81.041905.
89
[23] Shai S Shen-Orr et al. “Network motifs in the transcriptional regulation
network of Escherichia coli”. In: Nature genetics 31.1 (4 Apr. 2002), pp. 64–
68. DOI: 10.1103/PhysRevE.81.041905. URL: https://link.aps.
org/doi/10.1103/PhysRevE.81.041905.
[24] An-Liang Cheng and Pik-Yin Lai. “Phase transitions in optimized network
models”. In: Journal of Statistical Mechanics: Theory and Experiment 2020.9
(4 Sept. 2020), p. 093404. DOI: 10 . 1088 / 1742 - 5468 / abaece. URL:
https://dx.doi.org/10.1088/1742-5468/abaece.
[25] An-Liang Cheng and Pik-Yin Lai. “Optimized network properties in network growing models”. In: Chinese Journal of Physics 77 (4 Apr. 2022),
pp. 411–431. ISSN: 0577-9073. DOI: https://doi.org/10.1016/j.
cjph . 2022 . 02 . 008. URL: https : / / www . sciencedirect . com /
science/article/pii/S057790732200034X.
[26] Rong-Chih Chang, An-Liang Cheng, Pik-Yin Lai, et al. “Diverse phase
transitions in optimized directed network models with distinct inward
and outward node weights”. In: Physical Review E 107.3 (4 Apr. 2023),
p. 034312. DOI: 10 . 1103 / PhysRevE . 81 . 041905. URL: https : / /
link.aps.org/doi/10.1103/PhysRevE.81.041905.
[27] Paul Erd˝os, Alfréd Rényi, et al. “On the evolution of random graphs”. In:
Publ. Math. Inst. Hung. Acad. Sci 5.1 (4 Apr. 1960), pp. 17–60. DOI: 10 .
1103/PhysRevE.81.041905. URL: https://link.aps.org/doi/
10.1103/PhysRevE.81.041905.
[28] Giorgio Fagiolo. “Clustering in complex directed networks”. In: Phys. Rev.
E 76 (2 Aug. 2007), p. 026107. DOI: 10.1103/PhysRevE.76.026107.
URL: https : / / link . aps . org / doi / 10 . 1103 / PhysRevE . 76 .
026107.
[29] S. E. Ahnert and T. M. A. Fink. “Clustering signatures classify directed
networks”. In: Phys. Rev. E 78 (3 Sept. 2008), p. 036112. DOI: 10.1103/
PhysRevE.78.036112. URL: https://link.aps.org/doi/10.
1103/PhysRevE.78.036112.
[30] Réka Albert, Hawoong Jeong, and Albert-László Barabási. “Diameter of
the world-wide web”. In: nature 401.6749 (4 Apr. 1999), pp. 130–131. DOI:
10.1103/PhysRevE.81.041905. URL: https://link.aps.org/
doi/10.1103/PhysRevE.81.041905.
[31] Hawoong Jeong et al. “The large-scale organization of metabolic networks”. In: Nature 407.6804 (4 Apr. 2000), pp. 651–654. DOI: 10.1103/
PhysRevE.81.041905. URL: https://link.aps.org/doi/10.
1103/PhysRevE.81.041905.
90
[32] Holger Ebel, Lutz-Ingo Mielsch, and Stefan Bornholdt. “Scale-free topology of e-mail networks”. In: Physical review E 66.3 (4 Apr. 2002), p. 035103.
DOI: 10.1103/PhysRevE.81.041905. URL: https://link.aps.
org/doi/10.1103/PhysRevE.81.041905.
[33] Ivan Voitalov et al. “Scale-free networks well done”. In: Phys. Rev. Res. 1
(3 Oct. 2019), p. 033034. DOI: 10.1103/PhysRevResearch.1.033034.
URL: https://link.aps.org/doi/10.1103/PhysRevResearch.
1.033034.
[34] Jérôme Kunegis. “KONECT: The Koblenz Network Collection”. In: Proceedings of the 22nd International Conference on World Wide Web. Vol. 81.
WWW ’13 Companion. Rio de Janeiro, Brazil: Association for Computing
Machinery, Apr. 2013, 1343–1350. ISBN: 9781450320382. DOI: 10.1145/
2487788.2488173. URL: https://doi.org/10.1145/2487788.
2488173.
[35] Chi-Tin Shih et al. “Diverse community structures in the neuronal-level
connectome of the drosophila brain”. In: Neuroinformatics 18 (4 Apr. 2020),
pp. 267–281. DOI: 10.1103/PhysRevE.81.041905. URL: https://
link.aps.org/doi/10.1103/PhysRevE.81.041905.
[36] M. E. J. Newman and M. Girvan. “Finding and evaluating community
structure in networks”. In: Phys. Rev. E 69 (2 Feb. 2004), p. 026113. DOI:
10.1103/PhysRevE.69.026113. URL: https://link.aps.org/
doi/10.1103/PhysRevE.69.026113.
[37] E. A. Leicht and M. E. J. Newman. “Community Structure in Directed Networks”. In: Phys. Rev. Lett. 100 (11 Mar. 2008), p. 118703. DOI: 10.1103/
PhysRevLett.100.118703. URL: https://link.aps.org/doi/
10.1103/PhysRevLett.100.118703. |