Growing Networks with Preferential Linking

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

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

Clone this wiki locally

《Structure of Growing Networks with Preferential Linking》读书笔记[1]

 These were legitimate questions with consequences: Only researchers with a strong mathematical training could build on the scale-free concept. The resulting vacuum of understanding gave room for confusion and misinformation. This void was filled by the bombastic statements John Doyle made each time a journalist waved a mike in front of him. Then slowly the tide turned. <big>José Mendes, Sergey Dorogovtsev and Sid Redner</big> used a rate equation approach to put the continuum theory of scale-free networks on a firm mathematical footing [13,14]. Béla Bollo- bás and several colleagues in a landmark paper offered the exact proof of the scale-free property [15]. Shlomo Havlin and his students connected robustness to percolation theory [16] and Bollobás and Riordan waved in with an exact proof [17]. A string of discoveries started to document how deeply the scale-free property alters a network’s behavior, like Romualdo Pastor-Satorras and Alessandro Vespignani’s classic result on the disap- pearance of the epidemic threshold [18]. With that the community started to appreciate the central role the degree distribution plays in networks. As we will see throughout this textbook, virtually all network characteristics, from six degrees to robustness and community structure, must be inter- preted in its context. With hundreds of researchers attracted to networks by the many fundamental questions the field posed, gradually network science has taken shape.<ref>Barabasi, 2016, Network Science. Cambridge</ref>

Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2000). Structure of growing networks with preferential linking. Physical review letters, 85(21), 4633. [2]

Krapivsky, P. L., & Redner, S. (2002). Statistics of changes in lead node in connectivity-driven networks. Physical review letters, 89(25), 258703.[3]

Table of Contents

Growing Networks with Preferential Linking

BA模型的主要观点是网络增长与优先链接机制,即每一个时间步通过增添一个节点不断增长和新节点总是优先连接到度值较大的老节点上,而老节点获得一个新链接的概率是与网络中与这个节点度成比例的,经过长时间的演化,最终演化成幂律指数(γ)为3的网络。

在论文中,他们认为BA模型是一个特殊情况,两位作者通过一种主方程的方法对BA模型进行了优化。

  • (1)如果一个节点的初始吸引力为0(a = 0),那么所有的新连边都会集中到第一个节点,这样所有其他节点就没有机会得到新的进入的连边,这个时候γ=2,β=1;
  • (2)假设初始吸引力a = 1,γ=3,β=1/2,这种情形下就会生成BA模型,而当节点的初始吸引力a→∞,所有节点就会获得同等的对新连边的吸引力,这时连边的幂律分布会打破,这时γ→∞,β→0;
  • (3)
400px

Master equation

<math>p(q, s, t)</math> : the distribution of the connectivity q of the node s along the time t ( t = 1, 2, 3, ...)

5000px

构建增长网络的python代码

from networkx.utils import discrete_sequence

rr= []
degree_dist = range(100)

for i in range(10000):
    de = discrete_sequence(1,distribution=degree_dist)[0]
    rr.append(de)

plt.hist(rr)
plt.show()

P. L. Krapivsky and S. Redner, 2005. Network Growth by Copying, Phys. Rev. E, 71, 036118, 2005[4]

def gnc_graph(n, create_using=None, seed=None):
    """Return the growing network with 
       copying (GNC) digraph with n nodes.

    The GNC graph is built by adding nodes one 
    at a time with a link to one
    previously added node (chosen uniformly at random)
    and to all of that node's successors.

    Parameters
    ----------
    n : int
        The number of nodes for the generated graph.
    create_using : graph, optional (default DiGraph)
        Return graph of this type. The instance will be cleared.
    seed : hashable object, optional
        The seed for the random number generator.
    """
    if create_using is None:
        create_using = nx.DiGraph()
    elif not create_using.is_directed():
        raise nx.NetworkXError("Directed Graph required in create_using")

    if not seed is None:
        random.seed(seed)

    G=empty_graph(1,create_using)
    G.name="gnc_graph(%s)"%(n)

    if n==1:
        return G

    for source in range(1,n):
        target=random.randrange(0,source)
        for succ in G.successors(target):
            G.add_edge(source,succ)
        G.add_edge(source,target)

    return G

参考文献

Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2000). Structure of growing networks with preferential linking. Physical review letters, 85(21), 4633. PDF

↑ Barabasi, 2016, Network Science. Cambridge

↑ Krapivsky, P. L., & Redner, S. (2002). Statistics of changes in lead node in connectivity-driven networks. Physical review letters, 89(25), 258703. PDF

↑ P. L. Krapivsky and S. Redner, 2005. Network Growth by Copying, Phys. Rev. E, 71, 036118, 2005