Optimized network properties in directed network growing models

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：20

、訪客IP：3.135.247.94

姓名

張容誌(Rong-Chih Chang) 查詢紙本館藏

畢業系所

物理學系

論文名稱

(Optimized network properties in directed network growing models)

相關論文

★ Case study of an extended Fitzhugh-Nagumo model with chemical synaptic coupling and application to C. elegans functional neural circuits	★ 二維非彈性顆粒子之簇集現象
★ 螺旋狀高分子長鏈在拉力下之電腦模擬研究	★ 顆粒體複雜流動之研究
★ 高分子在二元混合溶劑之二維蒙地卡羅模擬研究	★ 帶電高分子吸附在帶電的表面上之研究
★ 自我纏繞繩節高分子之物理	★ 高分子鏈在強拉伸流場下之研究
★ 利用雷射破壞方法研究神經網路的連結及同步發火的行為	★ 最佳化網路成長模型的理論研究
★ 高分子鏈在交流電場或流場下的行為	★ 驟放式發火神經元的數值模擬
★ DNA在微通道的熱泳行為	★ 皮膚細胞增生與腫瘤生長之模擬
★ 耦合在非線性系統中的影響:模型探討以及非線性分析	★ 從網路節點時間序列分析網路特性並應用在體外培養神經及心臟細胞

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

複雜網路是一項十分重要的研究領域，在現實世界裡有很多系
統可以被網路所描述。我們透過將網路的連結對應到 Ising Model
的自旋來找出最佳化網路(最低成本)的解，除此之外，基於平均場
理論，我們還發展出一個演算法來有效地去計算最佳解。在之前的
研究裡，藉由不同的連結以及節點本身的分布，我們觀察到許多網
路結構的相變現象。在這篇論文裡，我們研究最佳化網路的一些網
路性質，像是聚集係數、最短路徑、度分布等等。我們假設真實的
網路往往是長時間的演化而形成的，這種演化結果必然是通過某種
最佳化的方法，我們的目標是想知道網路當中節點和連結的微觀性
質，跟最佳化的網路性質之間的關係。透過假設網路本身不同的微
觀性質，我們發現到在特定條件下，我們產生的最佳化網路具有類
似現實網路的一些現象，例如小世界網路和無尺度網路。

摘要(英)

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.

關鍵字(中)

★ 複雜網路
★ 最佳化網路
★ 易辛模型
★ 有向圖
★ 無尺度網路

關鍵字(英)

★ Complex network
★ Optimized network
★ Ising model
★ Directed graph
★ Scale-free network

論文目次

1 Introduction 1
2 Directed network growth model with microscopic distributions 5
2.1 Network growing Model A . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Network growing Model B . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Phase transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Clustering and minimal path length in optimized networks 14
3.1 Cluster Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Minimal path length . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Small-world effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Degree distributions of optimized networks 36
4.1 Unweighted nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Weighted nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Negative node weights . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 Comparison between optimized networks and real ones . . . . . 55
4.5 Relation between node weights and degrees . . . . . . . . . . . . 63
5 Motifs in optimized networks 69
5.1 3-node subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2 3-motifs in our optimized network . . . . . . . . . . . . . . . . . . 73
6 Conclusion 84
Bibliography 88

參考文獻

[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.

指導教授

黎璧賢(Pik-Yin Lai)

審核日期

2023-7-6

推文