分形网络

Wang Cheng-Jun edited this page Dec 19, 2016 · 1 revision

计算传播学是计算社会科学的重要分支。它主要关注人类传播行为的可计算性基础,以传播网络分析、传播文本挖掘、数据科学等为主要分析工具,(以非介入地方式)大规模地收集并分析人类传播行为数据,挖掘人类传播行为背后的模式和法则,分析模式背后的生成机制与基本原理,可以被广泛地应用于数据新闻和计算广告等场景,注重编程训练、数学建模、可计算思维。

Clone this wiki locally

Table of Contents

网络重整化

Algorithm to perform a box covering to calculate the fractal dimension of a complex networks using the MEMB algorithm in C. All algorithms are explained in C. Song, L. K. Gallos, S. Havlin, H. A. Makse, “How to calculate the fractal dimension of a complex network- the box covering algorithm”, J. Stat. Mech. , P03006 (2007). See paper inJSTAT. See enclosed “readme.txt” file for instructions.

Algorithm to calculate the fractal dimension of a network. This file includes MEMB, CBB and random covering algorithms for Python. This package requires networkx. See file header for comments on how to use it.

http://www-levich.engr.ccny.cuny.edu/webpage/hmakse/software-and-data/ http://www-levich.engr.ccny.cuny.edu/~hmakse/modules.py

Hernan Makse

  1. Sep 2008–present. Professor of Physics, Levich Institute and Department of Physics, City College of New York.
  2. Jan 2005–Sep 2008. Associate Professor of Physics, Levich Institute and Department of Physics, City College of New York.
  3. Sep 2000–Dec 2004. Assistant Professor of Physics, Levich Institute and Department of Physics, City College of New York.
  4. Sep 1997–Sep 2000. Postdoctoral Fellow, Schlumberger-Doll Research, Ridgefield, CT,
  5. Aug 1996–Sep 1997. Postdoctoral period shared between laboratories of Prof. R. C. Ball, Cavendish Laboratory, University of Cambridge and Prof. P.-G. de Gennes, Coll`ege de France, Paris.
  6. Ph.D. in Physics, Boston University (Prof. H. E. Stanley, advisor), 1993–1996.

Chaoming Song

  1. B.S. in physics, Fudan University, China, 1997-2001.
  2. M.S. in physics, City College of New York, 2001-2003.
  3. Ph.D. in physics, City College of New York, 2003-2008.
  4. Research Associate, Northeastern University, 2008-2012.
  5. Research Assistant Professor, Northeastern University, 2012-present.
  6. Assistant professor, Miami University
Chaoming Song, Shlomo Havlin, and Hernan A Makse. Self-similarity of complex networks. Nature, 433(7024):392–395, 2005.[1] 以box-covering的方法,Song等人将网络进行粗粒化处理,最终压缩为一个节点,如下图。

Networkre normalization

记一个网络节点数量为<math>N</math>,重整化所采用盒子覆盖法,盒子的大小记为<math>l_B</math>,所需要的盒子的数量记为<math>N_B(l_B)</math>。二者具有幂关系,即<math>N_B(l_B) \sim l_B^{-\alpha}</math>

通常写为:<math>N_B(l_B)/N \sim l_B^{-\alpha}</math>

Song等分析了四类复杂网络:WWW, 演员网络,蛋白质互动网络,细胞网络。如下图:

文件:Selfsimilar scalingSnip20160123 70.png

自相似的结果除了表现为盒子大小与盒子数量的关系之外,还表现在不同<math>l_B</math>的时候,网络度分布的不变性

 However, cluster growth is mainly influenced by the small-world character, so that the highly connected nodes, called hubs, are encountered many times and the same hub appears in most of the boxes, biasing thus the result. From Lazaros K. Gallos, Chaoming Song, Herna ́ n A. Makse. A review of fractality and self-similarity in complex networks. Physica A 386 (2007) 686–691 <ref>Lazaros K. Gallos, Chaoming Song, Herna ́ n A. Makse. A review of fractality and self-similarity in complex networks. Physica A 386 (2007) 686–691</ref>

盒子数量和度的两种分形维数

The renormalized network gives rise to a new probability distri bution of links, <math>P(k')</math>, which is invariant under the renormalization:

<math>P(k) \rightarrow P(k') \approx (k')^{-\gamma}</math>

the number of links <math>k'</math> of each node in the renormalized network versus the maximum number of links <math>k</math> in each box of the unrenormalized network exhibits a scaling law:

<math>k \rightarrow k' = s(l_B)k</math>

Empirically they find that the scaling factor <math>s (<1) </math> scales with <math>l_B</math> with a new exponent <math>d_k</math>:

<math>s(l_B) \approx l_B^{-d_k}</math>

分形网络的起源

Chaoming Song, Shlomo Havlin, and Hern ́an A Makse团队2006年继续分析了分形网络的问题[2],主要是提出一个可能的机制:

 In our previous work4, we discovered the fractal nature of organization in many real networks. However, the question of how these networks have evolved in time remains unanswered. We therefore launch a study of growth mechanisms to understand the simultaneous emergence of fractality, modularity, and the small-world effect, as well as the scale-free property in real-world complex networks.

从网络演化的角度看,一个稳健的网络需要分形特征。

 The ‘democratic’ rule of the seminal Erdos–Renyi model14 (where the nodes in the network are connected at random) was first invoked to explain the small-world effect. It was then replaced by the ‘rich-get-richer’ principle of preferential attachment9 to explain the scale-free property; a discovery carrying important implications on network vulnerability15,16

1000px

网络的动态增长可以看做与重整化相反的过程,在这个过程中网络结构特征随着时间演化并不发生变化。因此可以从增长的角度看网络重整化。

  1. 模式1,按照hub-hub相连的机制演化,产生无标度、小世界网络,但没有分形。
  2. 模式2, 按照nonhub-nonhub相连的机制演化,产生无标度、分形网络,但没有小世界。
因此可以把这两种机制混合起来,进行仿真模拟。

数学模型

 To link quantitatively the anticorrelation at all length scales to the emergence of fractality, we next develop a mathematical framework and demonstrate the mechanism for fractal network growth.

Song等人建立了一个数学模型来描述分形网络增长的机制。

  • <math>\widetilde{N}(t) = n \widetilde{N}(t-1)</math> (1)
  • <math>\widetilde{k}(t) = s \widetilde{k}(t-1)</math> (2)
  • <math>\widetilde{L}(t) + L_0 = \alpha( \widetilde{L}(t-1) + L_0 ) </math> (3)
<math>N, K, L</math>分别是节点数量、网络度、网络直径,其中<math>L_0</math>表示直径的特征长度(用来描述非分形网络)。第二个公式使得网络具备无标度特征。

缩略图

根据前面介绍 ,存在:

  • <math> N_B(l_B)/N \sim l_B^{-d_B} </math>
  • <math>k_B(l_B)/k_{hub} \sim l_B^{-d_k}</math>
根据论文附件的推导:
  • <math>d_B = \ln n / \ ln \alpha</math>
  • <math>d_k = \ln s / \ ln \alpha</math>
  • <math>\gamma =1 + \ln n / \ ln s</math>
 In general, the growth process is a stochastic combination of Mode I (with probability e) and Mode II (with probability 1 − e). For the intermediate (0 < e < 1), the model predicts finite fractal exponents dB and dk , and also bears the small-world property due to the presence of Mode I.

我们将盒子之间建立链接的链接的模式分为两种:1. 中心节点间相互吸引(hub-hub attraction), 2. 中心节点间相互排斥(hub-hub repulsion)。我们令模式1的概率为<math>e</math>, 模式2的概率则为<math>1-e</math>。

对于一个在时间<math>t-1</math>时度为<math>\tilde{k}(t-1)</math>的节点,我们定义下一个时间<math>t</math>时中心节点hub的链接数量是<math>\tilde{n_h}(t) </math>。此时,概率<math>e</math>满足:

<math>\tilde{n_h}(t) = e\tilde{k}(t-1)</math>。

类比时间演化与重整化,我们同样可以定义<math>n_h(l_B) </math>,并且定义<math>n_h(l_B) </math>与<math>k_B(l_B) </math>之间的比值为:

<math> \varepsilon (l_B) = n_h(l_B) / k_B(l_B) </math>

从小世界到分形

Rozenfeld, H. D., Song, C., & Makse, H. A. (2010)在PRL发表题为从小世界到分形的论文.[3]

文件:Snip20160121_66.png

其他研究

Radicchi, F., Ramasco, J. J., Barrat, A., & Fortunato, S. (2008). Complex networks renormalization: Flows and fixed points. Physical review letters, 101(14), 148701.[4]

Kim, J. S., Goh, K. I., Kahng, B., & Kim, D. (2007). Fractality and self-similarity in scale-free networks. New Journal of Physics, 9(6), 177. [5]

Goh, K. I., Salvi, G., Kahng, B., & Kim, D. (2006). Skeleton and fractal scaling in complex networks. Physical review letters, 96(1), 018701. Chicago [6]

参考文献

  1. ^ Chaoming Song, Shlomo Havlin, and Hernan A Makse. Self-similarity of complex networks. Nature, 433(7024):392–395, 2005.
  2. ^ Chaoming Song, Shlomo Havlin, and Hern ́an A Makse. Origins of fractality in the growth of complex networks. Nature Physics, 2(4):275–281, 2006.
  3. ^ Rozenfeld, H. D., Song, C., & Makse, H. A. (2010). Small-world to fractal transition in complex networks: a renormalization group approach. Physical review letters, 104(2), 025701.
  4. ^ Radicchi, F., Ramasco, J. J., Barrat, A., & Fortunato, S. (2008). Complex networks renormalization: Flows and fixed points. Physical review letters, 101(14), 148701.
  5. ^ Kim, J. S., Goh, K. I., Kahng, B., & Kim, D. (2007). Fractality and self-similarity in scale-free networks. New Journal of Physics, 9(6), 177. http://iopscience.iop.org/article/10.1088/1367-2630/9/6/177/fulltext/;jsessionid=BB81F2285EFBD0A74C29AB3970386C05.c2.iopscience.cld.iop.org
  6. ^ Goh, K. I., Salvi, G., Kahng, B., & Kim, D. (2006). Skeleton and fractal scaling in complex networks. Physical review letters, 96(1), 018701. Chicago

Category:传播网络