网络科学

任务

• 生产人:思无涯咿呀咿呀
• 上一个任务：无
• 下一个任务：信息审校:网络科学
• 任务完成时间：

具体内容

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes (or vertices) and the connections between the elements or actors as links (or edges). The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes (or vertices) and the connections between the elements or actors as links (or edges). The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."[1]

网络科学Network Science是一个研究复杂网络的学术领域，如通讯网络，计算机网络，生物网络，认知和语义网络，以及社会网络，主要由节点（顶点）表示不同元素或参与者，由连边表示元素和参与者之间的联系。这个领域的理论和方法包括数学的图理论，物理学的统计力学，计算机科学的数据挖掘和信息可视化，统计学的推理建模，社会学的社会结构。 美国国家研究委员会The United States National Research Council将网络科学定义为“研究物理、生物和社会现象的网络表征，从而得出这些现象的预测模型。” [1]

背景和历史

The study of networks has emerged in diverse disciplines as a means of analyzing complex relational data. The earliest known paper in this field is the famous Seven Bridges of Königsberg written by Leonhard Euler in 1736. Euler's mathematical description of vertices and edges was the foundation of graph theory, a branch of mathematics that studies the properties of pairwise relations in a network structure. The field of graph theory continued to develop and found applications in chemistry (Sylvester, 1878).

The study of networks has emerged in diverse disciplines as a means of analyzing complex relational data. The earliest known paper in this field is the famous Seven Bridges of Königsberg written by Leonhard Euler in 1736. Euler's mathematical description of vertices and edges was the foundation of graph theory, a branch of mathematics that studies the properties of pairwise relations in a network structure. The field of graph theory continued to develop and found applications in chemistry (Sylvester, 1878).

网络研究作为分析复杂关系数据的一种手段已经出现在不同的学科中。 在这个领域已知最早的论文是1736年 欧拉 Leonhard Euler 写的著名的柯尼斯堡七桥问题Seven Bridges of Königsberg。 欧拉对顶点和边的数学描述是图论的基础，这是一个研究网络结构中成对关系的性质的数学分支。 图理论的领域继续发展，并在化学中得到应用(Sylvester，1878)。

Dénes Kőnig, a Hungarian mathematician and professor, wrote the first book in Graph Theory, entitled "Theory of finite and infinite graphs", in 1936

Dénes Kőnig, a Hungarian mathematician and professor, wrote the first book in Graph Theory, entitled "Theory of finite and infinite graphs", in 1936 [2] 匈牙利数学家兼教授Dénes Kőnig在1936年写了图论的第一本书《有限图和无限图理论》Theory of finite and infinite graphs。

Moreno's sociogram of a 1st grade class.

In the 1930s Jacob Moreno, a psychologist in the Gestalt tradition, arrived in the United States. He developed the sociogram and presented it to the public in April 1933 at a convention of medical scholars. Moreno claimed that "before the advent of sociometry no one knew what the interpersonal structure of a group 'precisely' looked like" (Moreno, 1953). The sociogram was a representation of the social structure of a group of elementary school students. The boys were friends of boys and the girls were friends of girls with the exception of one boy who said he liked a single girl. The feeling was not reciprocated. This network representation of social structure was found so intriguing that it was printed in The New York Times (April 3, 1933, page 17). The sociogram has found many applications and has grown into the field of social network analysis.

In the 1930s Jacob Moreno, a psychologist in the Gestalt tradition, arrived in the United States. He developed the sociogram and presented it to the public in April 1933 at a convention of medical scholars. Moreno claimed that "before the advent of sociometry no one knew what the interpersonal structure of a group 'precisely' looked like" (Moreno, 1953). The sociogram was a representation of the social structure of a group of elementary school students. The boys were friends of boys and the girls were friends of girls with the exception of one boy who said he liked a single girl. The feeling was not reciprocated. This network representation of social structure was found so intriguing that it was printed in The New York Times (April 3, 1933, page 17). The sociogram has found many applications and has grown into the field of social network analysis.

20世纪30年代，格式塔传统的心理学家雅各布·莫雷诺Jacob Moreno来到美国。 在1933年4月的一次医学学者大会上，他在大会上展示了他制作的社网图 sociogram。 莫雷诺声称“在社会计量学出现之前，没有人知道一个群体的人际关系结构‘精确地’看起来像什么”(莫雷诺，1953)。 这张社网图展示一群小学生的社会结构。男孩是男孩的朋友，女孩是女孩的朋友，只有一个男孩说他喜欢另一个单身女孩但是没有得到回应。 这个网络展示的社会结构非常有趣，也被刊登在《纽约时报》上(1933年4月3日，第17页)。 社网图已经有许多的应用场景，并且已经发展成为社会网络分析social network analysis的一个子领域。

Probabilistic theory in network science developed as an offshoot of graph theory with Paul Erdős and Alfréd Rényi's eight famous papers on random graphs. For social networks the exponential random graph model or p* is a notational framework used to represent the probability space of a tie occurring in a social network. An alternate approach to network probability structures is the network probability matrix, which models the probability of edges occurring in a network, based on the historic presence or absence of the edge in a sample of networks.

Probabilistic theory in network science developed as an offshoot of graph theory with Paul Erdős and Alfréd Rényi's eight famous papers on random graphs. For social networks the exponential random graph model or p* is a notational framework used to represent the probability space of a tie occurring in a social network. An alternate approach to network probability structures is the network probability matrix, which models the probability of edges occurring in a network, based on the historic presence or absence of the edge in a sample of networks.

20世纪90年代，在Paul Erdős和Alfréd Rényi发表了8篇关于随机图的著名论文之后，网络科学中的概率论 Probabilistic theory 作为图论的一个分支发展起来了。 对于社交网络social network来说，指数随机图模型或p* (是一个记号框架），用来表示在一个社交网络中连边在概率空间发生的概率。 网络概率结构的另一种替代表示方法是网络概率矩阵，它根据网络样本中边的历史信息来计算这条边在网络中出现的概率。

In 1998, David Krackhardt and Kathleen Carley introduced the idea of a meta-network with the PCANS Model. They suggest that "all organizations are structured along these three domains, Individuals, Tasks, and Resources". Their paper introduced the concept that networks occur across multiple domains and that they are interrelated. This field has grown into another sub-discipline of network science called dynamic network analysis.

In 1998, David Krackhardt and Kathleen Carley introduced the idea of a meta-network with the PCANS Model. They suggest that "all organizations are structured along these three domains, Individuals, Tasks, and Resources". Their paper introduced the concept that networks occur across multiple domains and that they are interrelated. This field has grown into another sub-discipline of network science called dynamic network analysis.

1998年，David Krackhardt和Kathleen Carley提出了用PCANS模型构建元网络meta-network的想法。 他们建议所有的组织都通过“个人、任务和资源”来构建。 他们的论文介绍了新的网络概念，即网络发生在多个领域的且相互关联。 这个领域已经发展也成为网络科学的另一个子学科，叫做动态网络分析dynamic network analysis。

More recently other network science efforts have focused on mathematically describing different network topologies. Duncan Watts reconciled empirical data on networks with mathematical representation, describing the small-world network. Albert-László Barabási and Reka Albert developed the scale-free network which is a loosely defined network topology that contains hub vertices with many connections, that grow in a way to maintain a constant ratio in the number of the connections versus all other nodes. Although many networks, such as the internet, appear to maintain this aspect, other networks have long tailed distributions of nodes that only approximate scale free ratios.

More recently other network science efforts have focused on mathematically describing different network topologies. Duncan Watts reconciled empirical data on networks with mathematical representation, describing the small-world network. Albert-László Barabási and Reka Albert developed the scale-free network which is a loosely defined network topology that contains hub vertices with many connections, that grow in a way to maintain a constant ratio in the number of the connections versus all other nodes. Although many networks, such as the internet, appear to maintain this aspect, other networks have long tailed distributions of nodes that only approximate scale free ratios.

最近其他网络科学的研究致力于用数学的方式描述不同网络的拓扑结构。邓肯·瓦茨Duncan Watts 将网络上的经验数据与数学表达相结合，描述了小世界网络。 艾伯特-拉斯洛·巴拉巴西 Albert-László Barabási 和 Reka Albert发现了无标度网络，简单说就是包含Hub中心节点（连边数量很多的节点），且连边的数量和节点数量呈现常数比率的增长方式，即一个网络上节点的度（节点所在连边的数量）分布服从幂指数为2和3之间的幂律分布。尽管许多网络，比如互联网，似乎保持了这样的特性，但是其他网络的节点分布表现出长尾特性，仅仅是接近无标度比例。

思无涯咿呀咿呀（讨论）Albert-László Barabási and Reka Albert developed the scale-free network which is a loosely defined network topology that contains hub vertices with many connections, that grow in a way to maintain a constant ratio in the number of the connections versus all other nodes. 思无涯咿呀咿呀（讨论）这一段话怎么理解。

国防部倡议

The U.S. military first became interested in network-centric warfare as an operational concept based on network science in 1996. John A. Parmentola, the U.S. Army Director for Research and Laboratory Management, proposed to the Army’s Board on Science and Technology (BAST) on December 1, 2003 that Network Science become a new Army research area. The BAST, the Division on Engineering and Physical Sciences for the National Research Council (NRC) of the National Academies, serves as a convening authority for the discussion of science and technology issues of importance to the Army and oversees independent Army-related studies conducted by the National Academies. The BAST conducted a study to find out whether identifying and funding a new field of investigation in basic research, Network Science, could help close the gap between what is needed to realize Network-Centric Operations and the current primitive state of fundamental knowledge of networks.

The U.S. military first became interested in network-centric warfare as an operational concept based on network science in 1996. John A. Parmentola, the U.S. Army Director for Research and Laboratory Management, proposed to the Army’s Board on Science and Technology (BAST) on December 1, 2003 that Network Science become a new Army research area. The BAST, the Division on Engineering and Physical Sciences for the National Research Council (NRC) of the National Academies, serves as a convening authority for the discussion of science and technology issues of importance to the Army and oversees independent Army-related studies conducted by the National Academies. The BAST conducted a study to find out whether identifying and funding a new field of investigation in basic research, Network Science, could help close the gap between what is needed to realize Network-Centric Operations and the current primitive state of fundamental knowledge of networks.

1996年，美国军方第一次对网络中心战感兴趣，将其作为一个基于网络科学的军事概念。 2003年12月1日，美国陆军研究和实验室管理主任 John A. Parmentola 向陆军科学和技术委员会提议，网络科学成为陆军的一个新的研究领域。科学和技术委员会是美国国家学院国家研究委员会工程和物理科学司的下属部门，主要讨论对陆军重要的科学和技术问题，并且监督美国国家学院进行的与陆军相关的独立研究。 科学和技术委员会进行了一项研究，他们想通过确定和资助一个新的研究领域的基础研究：网络科学，希望可以帮助找到网络中心战所必须的知识，从而缩小实现网络中心战与当前网络科学理论基础的差距。

As a result, the BAST issued the NRC study in 2005 titled Network Science (referenced above) that defined a new field of basic research in Network Science for the Army. Based on the findings and recommendations of that study and the subsequent 2007 NRC report titled Strategy for an Army Center for Network Science, Technology, and Experimentation, Army basic research resources were redirected to initiate a new basic research program in Network Science. To build a new theoretical foundation for complex networks, some of the key Network Science research efforts now ongoing in Army laboratories address:

因此，科学和技术委员在2005年发布了NRC的研究报告，题为《网络科学定义了美国陆军网络科学基础研究新领域》。 基于这项研究的发现和建议，以及随后2007年 NRC 题为基于网络科学、技术和实战的战略研究报告，陆军基础研究资源被重新投入在网络科学的一个新的基础研究项目。为了建立复杂网络的全新的理论基础，美国陆军实验室正在进行的一些关键的网络科学研究工作致力于:

• Mathematical models of network behavior to predict performance with network size, complexity, and environment
• Optimized human performance required for network-enabled warfare
• Networking within ecosystems and at the molecular level in cells.

• 网络行为的数学模型，以预测网络规模、复杂度和环境的表现
• 网络化战争network-enabled warfare所需的最佳人类表现
• 生态系统中基于细胞分子层面的网络建模

As initiated in 2004 by Frederick I. Moxley with support he solicited from David S. Alberts, the Department of Defense helped to establish the first Network Science Center in conjunction with the U.S. Army at the United States Military Academy (USMA). Under the tutelage of Dr. Moxley and the faculty of the USMA, the first interdisciplinary undergraduate courses in Network Science were taught to cadets at West Point. In order to better instill the tenets of network science among its cadre of future leaders, the USMA has also instituted a five-course undergraduate minor in Network Science.

正如2004年 David S. Alberts支持Frederick I. Moxley那样，国防部帮助美国陆军一起在美国军事学院(USMA)建立了第一个网络科学中心。 在Moxley博士和美国军事学院(USMA)研究员的指导下，西点军校开设了首个网络科学本科生课程。为了更好地向其未来领导干部灌输网络科学的信条，美国军事学院还在网络科学下设置了一个5节课本科生辅修课程。

In 2006, the U.S. Army and the United Kingdom (UK) formed the Network and Information Science International Technology Alliance, a collaborative partnership among the Army Research Laboratory, UK Ministry of Defense and a consortium of industries and universities in the U.S. and UK. The goal of the alliance is to perform basic research in support of Network- Centric Operations across the needs of both nations.

2006年，美国陆军和英国成立了网络和信息科学国际技术联盟，这是美国陆军研究实验室、英国国防部以及美国和英国的工业和大学联盟之间的合作伙伴关系。 该联盟的目标是进行基础研究，以支持两国需要的网络中心作战。

In 2009, the U.S. Army formed the Network Science CTA, a collaborative research alliance among the Army Research Laboratory, CERDEC, and a consortium of about 30 industrial R&D labs and universities in the U.S. The goal of the alliance is to develop a deep understanding of the underlying commonalities among intertwined social/cognitive, information, and communications networks, and as a result improve our ability to analyze, predict, design, and influence complex systems interweaving many kinds of networks.

Subsequently, as a result of these efforts, the U.S. Department of Defense has sponsored numerous research projects that support Network Science. 2009年，美国陆军成立了网络科学 CTA，这是一个由陆军研究实验室、 CERDEC 和美国大约30个工业研发实验室和大学组成的联盟之间的合作研究联盟。 这个联盟的目标是深入理解交织在一起的社会 / 认知、信息和通信网络之间的潜在共性，从而提高我们分析、预测、设计和影响交织在多种网络中的复杂系统的能力。

随后，作为这些努力的结果，美国国防部赞助了许多支持网络科学的研究项目。

Network properties

Often, networks have certain attributes that can be calculated to analyze the properties & characteristics of the network. The behavior of these network properties often define network models and can be used to analyze how certain models contrast to each other. Many of the definitions for other terms used in network science can be found in Glossary of graph theory.

通常，网络具有一些可计算的属性来分析网络的性质和特征。 这些网络属性的特征通常被定义为网络模型 ，可用于对比分析不同模型之间的差异。 网络科学中使用的许多其他术语的定义可以在图论术语表Glossary of graph theory中找到。

Size

The size of a network can refer to the number of nodes [math]\displaystyle{ N }[/math] or, less commonly, the number of edges [math]\displaystyle{ E }[/math] which (for connected graphs with no multi-edges) can range from [math]\displaystyle{ N-1 }[/math] (a tree) to [math]\displaystyle{ E_{\max} }[/math] (a complete graph). In the case of a simple graph (a network in which at most one (undirected) edge exists between each pair of vertices, and in which no vertices connect to themselves), we have [math]\displaystyle{ E_{\max}=\tbinom N2=N(N-1)/2 }[/math]; for directed graphs (with no self-connected nodes), [math]\displaystyle{ E_{\max}=N(N-1) }[/math]; for directed graphs with self-connections allowed, [math]\displaystyle{ E_{\max}=N^2 }[/math]. In the circumstance of a graph within which multiple edges may exist between a pair of vertices, [math]\displaystyle{ E_{\max}=\infty }[/math].

规模

网络的规模可以由节点的个数[math]\displaystyle{ N }[/math]，或者，少数情况下，连边的数量[math]\displaystyle{ E }[/math]（对于没有重边的连通图），连边的个数E的范围一般是从[math]\displaystyle{ N-1 }[/math] （看做是一个树）到[math]\displaystyle{ E_{\max} }[/math] （看做是一个完全图）。在简单图的例子中（网络中在每对节点之间至多存在一条(无向)边，并且没有节点连向自己），可以计算[math]\displaystyle{ E_{\max}=\tbinom N2=N(N-1)/2 }[/math]；对于有向图（没有自环self-connected的节点），[math]\displaystyle{ E_{\max}=N(N-1) }[/math]；对于有向图且允许存在自环的节点，[math]\displaystyle{ E_{\max}=N^2 }[/math].还有另外一种特殊情况就是一对节点之间存在重边， [math]\displaystyle{ E_{\max}=\infty }[/math].

Density

The density [math]\displaystyle{ D }[/math] of a network is defined as a ratio of the number of edges [math]\displaystyle{ E }[/math] to the number of possible edges in a network with [math]\displaystyle{ N }[/math] nodes, given (in the case of simple graphs) by the binomial coefficient [math]\displaystyle{ \tbinom N2 }[/math], giving [math]\displaystyle{ D =\frac{E-(N-1)}{Emax - (N-1)} = \frac{2(E-N+1)}{N(N-3)+2} }[/math] Another possible equation is [math]\displaystyle{ D = \frac{T-2N+2}{N(N-3)+2}, }[/math] whereas the ties [math]\displaystyle{ T }[/math] are unidirectional (Wasserman & Faust 1994). This gives a better overview over the network density, because unidirectional relationships can be measured.

密度 Density

网络的密度 [math]\displaystyle{ D }[/math] 通常定义为网络中已有的连边数量[math]\displaystyle{ E }[/math]与[math]\displaystyle{ N }[/math] 都连接的所有可能边数的的比值，例如在简单图中，所有可能的连边总数可由二项式系数binomial coefficient计算得到 [math]\displaystyle{ \tbinom N2 }[/math]，所以网络的密度[math]\displaystyle{ D =\frac{E-(N-1)}{Emax - (N-1)} = \frac{2(E-N+1)}{N(N-3)+2} }[/math]，另外一个可能的等式就是[math]\displaystyle{ D = \frac{T-2N+2}{N(N-3)+2} }[/math] ，而[math]\displaystyle{ T }[/math] 节是没有方向的(Wasserman & Faust 1994)。这为网络密度提供了更好的概述，因为可以度量单向关系。

Planar Network Density

The density [math]\displaystyle{ D }[/math] of a network, where there is no intersection between edges, is defined as a ratio of the number of edges [math]\displaystyle{ E }[/math] to the number of possible edges in a network with [math]\displaystyle{ N }[/math] nodes, given by a graph with no intersecting edges [math]\displaystyle{ (E_{\max}=3N-6) }[/math], giving [math]\displaystyle{ D = \frac{E-N+1}{2N-5}. }[/math]

平面网络密度 Planar Network Density

一个网络的密度[math]\displaystyle{ D }[/math] 被定义为连边数量 [math]\displaystyle{ E }[/math]和节点数量[math]\displaystyle{ N }[/math]的比值，

平均度 Average degree

The degree [math]\displaystyle{ k }[/math] of a node is the number of edges connected to it. Closely related to the density of a network is the average degree, [math]\displaystyle{ \langle k\rangle = \tfrac{2E}{N} }[/math] (or, in the case of directed graphs, [math]\displaystyle{ \langle k\rangle = \tfrac{E}{N} }[/math], the former factor of 2 arising from each edge in an undirected graph contributing to the degree of two distinct vertices). In the ER random graph model ([math]\displaystyle{ G(N,p) }[/math]) we can compute the expected value of [math]\displaystyle{ \langle k \rangle }[/math] (equal to the expected value of [math]\displaystyle{ k }[/math] of an arbitrary vertex): a random vertex has [math]\displaystyle{ N-1 }[/math] other vertices in the network available, and with probability [math]\displaystyle{ p }[/math], connects to each. Thus, [math]\displaystyle{ \mathbb{E}[\langle k \rangle]=\mathbb{E}[k]= p(N-1) }[/math].

一个节点连接的边数称为节点的度[math]\displaystyle{ k }[/math]，网络中的密度和节点的度有密切的关系，网络中所有节点的度的平均值称为网络的平均度，其中平均度[math]\displaystyle{ \langle k\rangle = \tfrac{2E}{N} }[/math] （或者在一些有向图中， [math]\displaystyle{ \langle k\rangle = \tfrac{E}{N} }[/math]，分子中多了一个2倍的关系，是因为有向图中节点的度是无向图中节点度的2倍），在Erdős–Rényi随机图模型中,([math]\displaystyle{ G(N,p) }[/math]) ，我们可以计算[math]\displaystyle{ \langle k \rangle }[/math] 的值，（等于[math]\displaystyle{ k }[/math]个随机点的期望值），一个随机点与其他[math]\displaystyle{ N-1 }[/math] 点相连，假设这些点两两相连的概率为[math]\displaystyle{ p }[/math]，因为可以计算度的期望：[math]\displaystyle{ \mathbb{E}[\langle k \rangle]=\mathbb{E}[k]= p(N-1) }[/math].

平均最短路径长度（特征路径长度）

The average shortest path length is calculated by finding the shortest path between all pairs of nodes, and taking the average over all paths of the length thereof (the length being the number of intermediate edges contained in the path, i.e., the distance [math]\displaystyle{ d_{u,v} }[/math] between the two vertices [math]\displaystyle{ u,v }[/math] within the graph). This shows us, on average, the number of steps it takes to get from one member of the network to another. The behavior of the expected average shortest path length (that is, the ensemble average of the average shortest path length) as a function of the number of vertices [math]\displaystyle{ N }[/math] of a random network model defines whether that model exhibits the small-world effect; if it scales as [math]\displaystyle{ O(\ln N) }[/math], the model generates small-world nets. For faster-than-logarithmic growth, the model does not produce small worlds. The special case of [math]\displaystyle{ O(\ln\ln N) }[/math] is known as ultra-small world effect.

平均最短路径长度的计算方法是找到所有节点对之间的最短路径，并取其长度所有路径的平均值(其长度为路径中包含的中间边的数目，即图中两个顶点之间的距离{ displaystyle d { u，v }})。 这向我们展示了从网络中的一个成员到另一个成员所需的平均步数。 期望平均最短路径长度(即平均最短路径长度的总体均值)作为一个随机网络模型的顶点数 n } n 的函数的行为定义了该模型是否表现出小世界效应; 如果它缩放为{ displaystyle o (ln n)} ，则该模型生成小世界网。 对于比对数更快的增长，该模型不会产生小世界。 超小世界效应(ultra-small world effect)是超小世界效应的特例。

Diameter of a network

As another means of measuring network graphs, we can define the diameter of a network as the longest of all the calculated shortest paths in a network. It is the shortest distance between the two most distant nodes in the network. In other words, once the shortest path length from every node to all other nodes is calculated, the diameter is the longest of all the calculated path lengths. The diameter is representative of the linear size of a network. If node A-B-C-D are connected, going from A->D this would be the diameter of 3 (3-hops, 3-links).模板:Fact

Clustering coefficient

The clustering coefficient is a measure of an "all-my-friends-know-each-other" property. This is sometimes described as the friends of my friends are my friends. More precisely, the clustering coefficient of a node is the ratio of existing links connecting a node's neighbors to each other to the maximum possible number of such links. The clustering coefficient for the entire network is the average of the clustering coefficients of all the nodes. A high clustering coefficient for a network is another indication of a small world.

The clustering coefficient of the [math]\displaystyle{ i }[/math]'th node is

[math]\displaystyle{ C_i = {2e_i\over k_i{(k_i - 1)}}\,, }[/math]

where [math]\displaystyle{ k_i }[/math] is the number of neighbours of the [math]\displaystyle{ i }[/math]'th node, and [math]\displaystyle{ e_i }[/math] is the number of connections between these neighbours. The maximum possible number of connections between neighbors is, then,

[math]\displaystyle{ {\binom {k}{2}} = {{k(k-1)}\over 2}\,. }[/math]

From a probabalistic standpoint, the expected local clustering coefficient is the likelihood of a link existing between two arbitrary neighbors of the same node.

Connectedness

The way in which a network is connected plays a large part into how networks are analyzed and interpreted. Networks are classified in four different categories:

• Clique/Complete Graph: a completely connected network, where all nodes are connected to every other node. These networks are symmetric in that all nodes have in-links and out-links from all others.
• Giant Component: A single connected component which contains most of the nodes in the network.
• Weakly Connected Component: A collection of nodes in which there exists a path from any node to any other, ignoring directionality of the edges.
• Strongly Connected Component: A collection of nodes in which there exists a directed path from any node to any other.

Node centrality

Main article: Centrality

Centrality indices produce rankings which seek to identify the most important nodes in a network model. Different centrality indices encode different contexts for the word "importance." The betweenness centrality, for example, considers a node highly important if it form bridges between many other nodes. The eigenvalue centrality, in contrast, considers a node highly important if many other highly important nodes link to it. Hundreds of such measures have been proposed in the literature.

Centrality indices are only accurate for identifying the most central nodes. The measures are seldom, if ever, meaningful for the remainder of network nodes. Also, their indications are only accurate within their assumed context for importance, and tend to "get it wrong" for other contexts. For example, imagine two separate communities whose only link is an edge between the most junior member of each community. Since any transfer from one community to the other must go over this link, the two junior members will have high betweenness centrality. But, since they are junior, (presumably) they have few connections to the "important" nodes in their community, meaning their eigenvalue centrality would be quite low.

The concept of centrality in the context of static networks was extended, based on empirical and theoretical research, to dynamic centrality in the context of time-dependent and temporal networks.

Node influence

Main article: Node influence metric

Limitations to centrality measures have led to the development of more general measures. Two examples are the accessibility, which uses the diversity of random walks to measure how accessible the rest of the network is from a given start node, and the expected force, derived from the expected value of the force of infection generated by a node. Both of these measures can be meaningfully computed from the structure of the network alone.

Network models

Network models serve as a foundation to understanding interactions within empirical complex networks. Various random graph generation models produce network structures that may be used in comparison to real-world complex networks. 网络模型是理解经验上复杂网络内相互作用的基础，各种各样的随机图生成模型生成的网络结构可与现实中的复杂网络进行比较。

Erdős–Rényi random graph model

文件:ER model.svg

This Erdős–Rényi model is generated with N = 4 nodes. For each edge in the complete graph formed by all N nodes, a random number is generated and compared to a given probability. If the random number is less than p, an edge is formed on the model.

The Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is used for generating random graphs in which edges are set between nodes with equal probabilities. It can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

To generate an Erdős–Rényi model [math]\displaystyle{ G(n, p) }[/math] two parameters must be specified: the total number of nodes n and the probability p that a random pair of nodes has an edge.

Because the model is generated without bias to particular nodes, the degree distribution is binomial: for a randomly chosen vertex [math]\displaystyle{ v }[/math],

[math]\displaystyle{ P(\deg(v) = k) = {n-1\choose k} p^k (1-p)^{n-1-k}. }[/math]

In this model the clustering coefficient is 0 a.s. The behavior of [math]\displaystyle{ G(n, p) }[/math] can be broken into three regions.

Subcritical [math]\displaystyle{ n p \lt 1 }[/math]: All components are simple and very small, the largest component has size [math]\displaystyle{ |C_1| = O(\log n) }[/math];

Critical [math]\displaystyle{ n p = 1 }[/math]: [math]\displaystyle{ |C_1| = O(n^\frac{2}{3}) }[/math];

Supercritical [math]\displaystyle{ n p \gt 1 }[/math]:[math]\displaystyle{ |C_1| \approx yn }[/math] where [math]\displaystyle{ y = y(n p) }[/math] is the positive solution to the equation [math]\displaystyle{ e^{-p n y }=1-y }[/math].

The largest connected component has high complexity. All other components are simple and small [math]\displaystyle{ |C_2| = O(\log n) }[/math].

Erdős–Rényi 随机图模型

以Paul Erdős和Alfréd Rényi命名的Erdős–Rényi 模型用于生成随机图，它的边是等概率连接的节点的集合。随机图可以用来证明概率方法中满足某些条件的图的存在性，或者对几乎所有图给出某个性质的严格定义。

生成Erdős–Rényi 模型 [math]\displaystyle{ G(n, p) }[/math]需要给定两个参数：总结点数n和任意两个节点间有连接的概率p 。

由于模型是在不偏向特定节点的情况下生成的，因此度分布是二项分布：对任意的节点[math]\displaystyle{ v }[/math] ： [math]\displaystyle{ P(\deg(v) = k) = {n-1\choose k} p^k (1-p)^{n-1-k}. }[/math]

Erdős–Rényi 模型的聚集系数是0 a.s。 [math]\displaystyle{ G(n, p) }[/math] 的行为可以分为三个区域：

亚临界 [math]\displaystyle{ n p \lt 1 }[/math]: 所有组分都是简单而且很小的，其中最大组分的大小 [math]\displaystyle{ |C_1| = O(\log n) }[/math];

临界 [math]\displaystyle{ n p = 1 }[/math]: [math]\displaystyle{ |C_1| = O(n^\frac{2}{3}) }[/math];

超临界 [math]\displaystyle{ n p \gt 1 }[/math]:[math]\displaystyle{ |C_1| \approx yn }[/math] 其中 [math]\displaystyle{ y = y(n p) }[/math] 是方程 [math]\displaystyle{ e^{-p n y }=1-y }[/math]的正根。

最大的连通组分复杂性最高，其他所有组分都是简单而且很小的 [math]\displaystyle{ |C_2| = O(\log n) }[/math].

Configuration model

The configuration model takes a degree sequence or degree distribution (which subsequently is used to generate a degree sequence) as the input, and produces randomly connected graphs in all respects other than the degree sequence. This means that for a given choice of the degree sequence, the graph is chosen uniformly at random from the set of all graphs that comply with this degree sequence. The degree [math]\displaystyle{ k }[/math] of a randomly chosen vertex is an independent and identically distributed random variable with integer values. When [math]\displaystyle{ \mathbb E [k^2] - 2 \mathbb E [k]\gt 0 }[/math], the configuration graph contains the giant connected component, which has infinite size. The rest of the components have finite sizes, which can be quantified with the notion of the size distribution. The probability [math]\displaystyle{ w(n) }[/math] that a randomly sampled node is connected to a component of size [math]\displaystyle{ n }[/math] is given by convolution powers of the degree distribution:[math]\displaystyle{ w(n)=\begin{cases} \frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n\gt 1, \\ u(0) & n=1, \end{cases} }[/math]where [math]\displaystyle{ u(k) }[/math] denotes the degree distribution and [math]\displaystyle{ u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]} }[/math]. The giant component can be destroyed by randomly removing the critical fraction [math]\displaystyle{ p_c }[/math] of all edges. This process is called percolation on random networks. When the second moment of the degree distribution is finite, [math]\displaystyle{ \mathbb E [k^2]\lt \infty }[/math], this critical edge fraction is given by [math]\displaystyle{ p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]} }[/math], and the average vertex-vertex distance [math]\displaystyle{ l }[/math] in the giant component scales logarithmically with the total size of the network, [math]\displaystyle{ l = O(\log N) }[/math].

In the directed configuration model, the degree of a node is given by two numbers, in-degree [math]\displaystyle{ k_\text{in} }[/math] and out-degree [math]\displaystyle{ k_\text{out} }[/math], and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that [math]\displaystyle{ \mathbb E [k_\text{in}]=\mathbb E [k_\text{out}] }[/math]. The directed configuration model contains the giant component iff[math]\displaystyle{ 2\mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}k_\text{out}] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}^2] +\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in} k_\text{out}]^2 \gt 0. }[/math]Note that [math]\displaystyle{ \mathbb E [k_\text{in}] }[/math] and [math]\displaystyle{ \mathbb E [k_\text{out}] }[/math] are equal and therefore interchangeable in the latter inequality. The probability that a randomly chosen vertex belongs to a component of size [math]\displaystyle{ n }[/math] is given by:[math]\displaystyle{ h_\text{in}(n)=\frac{\mathbb E[k_{in}]}{n-1} \tilde u_\text{in}^{*n}(n-2), \;n\gt 1, \; \tilde u_\text{in}=\frac{k_\text{in}+1}{\mathbb E[k_\text{in}]}\sum\limits_{k_\text{out}\geq 0}u(k_\text{in}+1,k_\text{out}), }[/math]for in-components, and

[math]\displaystyle{ h_\text{out}(n)=\frac{\mathbb E[k_\text{out}]}{n-1} \tilde u_\text{out}^{*n}(n-2), \;n\gt 1, \;\tilde u_\text{out}=\frac{k_\text{out}+1}{\mathbb E[k_\text{out}]}\sum\limits_{k_\text{in}\geq0}u(k_\text{in},k_\text{out}+1), }[/math]

for out-components.

配置模型

配置模型以一个度序列 或度分布 （用于生成度序列）作为输入, 生成除了度序列外各方面随机连接的图。这意味着对于给定的度序列，图是一致随机地从符合这个度序列的所有图的集合中选择的。图中任意节点的度[math]\displaystyle{ k }[/math]是一个独立同分布，其值为整数。When [math]\displaystyle{ \mathbb E [k^2] - 2 \mathbb E [k]\gt 0 }[/math], the configuration graph contains the giant connected component, which has infinite size. The rest of the components have finite sizes, which can be quantified with the notion of the size distribution. The probability [math]\displaystyle{ w(n) }[/math] that a randomly sampled node is connected to a component of size [math]\displaystyle{ n }[/math] is given by convolution powers of the degree distribution:[math]\displaystyle{ w(n)=\begin{cases} \frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n\gt 1, \\ u(0) & n=1, \end{cases} }[/math]where [math]\displaystyle{ u(k) }[/math] denotes the degree distribution and [math]\displaystyle{ u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]} }[/math]. The giant component can be destroyed by randomly removing the critical fraction [math]\displaystyle{ p_c }[/math] of all edges. This process is called percolation on random networks. When the second moment of the degree distribution is finite, [math]\displaystyle{ \mathbb E [k^2]\lt \infty }[/math], this critical edge fraction is given by [math]\displaystyle{ p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]} }[/math], and the average vertex-vertex distance [math]\displaystyle{ l }[/math] in the giant component scales logarithmically with the total size of the network, [math]\displaystyle{ l = O(\log N) }[/math].

In the directed configuration model, the degree of a node is given by two numbers, in-degree [math]\displaystyle{ k_\text{in} }[/math] and out-degree [math]\displaystyle{ k_\text{out} }[/math], and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that [math]\displaystyle{ \mathbb E [k_\text{in}]=\mathbb E [k_\text{out}] }[/math]. The directed configuration model contains the giant component iff[math]\displaystyle{ 2\mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}k_\text{out}] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}^2] +\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in} k_\text{out}]^2 \gt 0. }[/math]Note that [math]\displaystyle{ \mathbb E [k_\text{in}] }[/math] and [math]\displaystyle{ \mathbb E [k_\text{out}] }[/math] are equal and therefore interchangeable in the latter inequality. The probability that a randomly chosen vertex belongs to a component of size [math]\displaystyle{ n }[/math] is given by:[math]\displaystyle{ h_\text{in}(n)=\frac{\mathbb E[k_{in}]}{n-1} \tilde u_\text{in}^{*n}(n-2), \;n\gt 1, \; \tilde u_\text{in}=\frac{k_\text{in}+1}{\mathbb E[k_\text{in}]}\sum\limits_{k_\text{out}\geq 0}u(k_\text{in}+1,k_\text{out}), }[/math]for in-components, and

[math]\displaystyle{ h_\text{out}(n)=\frac{\mathbb E[k_\text{out}]}{n-1} \tilde u_\text{out}^{*n}(n-2), \;n\gt 1, \;\tilde u_\text{out}=\frac{k_\text{out}+1}{\mathbb E[k_\text{out}]}\sum\limits_{k_\text{in}\geq0}u(k_\text{in},k_\text{out}+1), }[/math]

for out-components.

Watts–Strogatz small world model

文件:Watts-Strogatz-rewire.png

The Watts and Strogatz model uses the concept of rewiring to achieve its structure. The model generator will iterate through each edge in the original lattice structure. An edge may changed its connected vertices according to a given rewiring probability. [math]\displaystyle{ \langle k\rangle = 4 }[/math] in this example.

The Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties.

An initial lattice structure is used to generate a Watts–Strogatz model. Each node in the network is initially linked to its [math]\displaystyle{ \langle k\rangle }[/math] closest neighbors. Another parameter is specified as the rewiring probability. Each edge has a probability [math]\displaystyle{ p }[/math] that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is [math]\displaystyle{ pE = pN\langle k\rangle/2 }[/math].

As the Watts–Strogatz model begins as non-random lattice structure, it has a very high clustering coefficient along with high average path length. Each rewire is likely to create a shortcut between highly connected clusters. As the rewiring probability increases, the clustering coefficient decreases slower than the average path length. In effect, this allows the average path length of the network to decrease significantly with only slightly decreases in clustering coefficient. Higher values of p force more rewired edges, which in effect makes the Watts–Strogatz model a random network.

文件:Watts-Strogatz-rewire.png

Watts–Strogatz 模型利用重连接的概念构造小世界网络结构。模型生成器会遍历初始的规则网络的所有边，每一条边会以给定的重连接概率改变它两端的节点，例如[math]\displaystyle{ \langle k\rangle = 4 }[/math]。

Watts–Strogatz 模型是一个随机图生成模型，能够产生具有小世界性质的网络。

Watts–Strogatz 模型在一个初始的规则网络的基础上生成，初始网络中每个节点与它的[math]\displaystyle{ \langle k\rangle }[/math]个最近邻节点连接。给定另外一个参数重连接概率，每条边以[math]\displaystyle{ p }[/math]的概率在图中随机重连。该模型中重连接边数的期望值为[math]\displaystyle{ pE = pN\langle k\rangle/2 }[/math]。

由于Watts–Strogatz 模型的初始网络具有非随机的规则结构，它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率[math]\displaystyle{ p }[/math]会导致更多的边重新连接，这实际上使Watts Strogatz模型趋于随机网络。

Barabási–Albert (BA) preferential attachment model

The Barabási–Albert model is a random network model used to demonstrate a preferential attachment or a "rich-get-richer" effect. In this model, an edge is most likely to attach to nodes with higher degrees.The network begins with an initial network of m₀ nodes. m₀ ≥ 2 and the degree of each node in the initial network should be at least 1, otherwise it will always remain disconnected from the rest of the network.

The Barabási–Albert model is a random network model used to demonstrate a preferential attachment or a "rich-get-richer" effect. In this model, an edge is most likely to attach to nodes with higher degrees. The network begins with an initial network of m0 nodes. m0 ≥ 2 and the degree of each node in the initial network should be at least 1, otherwise it will always remain disconnected from the rest of the network.

Barabási–Albert (BA) 优先链接模型

BA模型是一个随机网络模型，用于说明偏好依附效应（优先链接）preferential attachment或“富人越富”效应。 在这个模型中，边最有可能附着在度数较高的节点上。 这个网络从一个 m0节点的初始网络开始。 M0≥2，初始网络中每个节点的度至少为1，否则它将始终与网络的其余部分断开。

In the BA model, new nodes are added to the network one at a time. Each new node is connected to [math]\displaystyle{ m }[/math] existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability p_i that the new node is connected to node i is

[math]\displaystyle{ p_i = \frac{k_i}{\sum_j k_j}, }[/math]

where k_i is the degree of node i. Heavily linked nodes ("hubs") tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. The new nodes have a "preference" to attach themselves to the already heavily linked nodes.

文件:Barabasi-albert model degree distribution.svg

The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.

The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form:

[math]\displaystyle{ P(k)\sim k^{-3} \, }[/math]

Hubs exhibit high betweenness centrality which allows short paths to exist between nodes. As a result, the BA model tends to have very short average path lengths. The clustering coefficient of this model also tends to 0. While the diameter, D, of many models including the Erdős Rényi random graph model and several small world networks is proportional to log N, the BA model exhibits D~loglogN (ultrasmall world). Note that the average path length scales with N as the diameter.

Mediation-driven attachment (MDA) model

In the mediation-driven attachment (MDA) model in which a new node coming with [math]\displaystyle{ m }[/math] edges picks an existing connected node at random and then connects itself not with that one but with [math]\displaystyle{ m }[/math] of its neighbors chosen also at random. The probability [math]\displaystyle{ \Pi(i) }[/math] that the node [math]\displaystyle{ i }[/math] of the existing node picked is

[math]\displaystyle{ \Pi(i) = \frac{k_i} N \frac{ \sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}. }[/math]

The factor [math]\displaystyle{ \frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i} }[/math] is the inverse of the harmonic mean (IHM) of degrees of the [math]\displaystyle{ k_i }[/math] neighbors of a node [math]\displaystyle{ i }[/math]. Extensive numerical investigation suggest that for an approximately [math]\displaystyle{ m\gt 14 }[/math] the mean IHM value in the large [math]\displaystyle{ N }[/math] limit becomes a constant which means [math]\displaystyle{ \Pi(i) \propto k_i }[/math]. It implies that the higher the links (degree) a node has, the higher its chance of gaining more links since they can be reached in a larger number of ways through mediators which essentially embodies the intuitive idea of rich get richer mechanism (or the preferential attachment rule of the Barabasi–Albert model). Therefore, the MDA network can be seen to follow the PA rule but in disguise.

However, for [math]\displaystyle{ m=1 }[/math] it describes the winner takes it all mechanism as we find that almost [math]\displaystyle{ 99\% }[/math] of the total nodes have degree one and one is super-rich in degree. As [math]\displaystyle{ m }[/math] value increases the disparity between the super rich and poor decreases and as [math]\displaystyle{ m\gt 14 }[/math] we find a transition from rich get super richer to rich get richer mechanism.

Fitness model

Another model where the key ingredient is the nature of the vertex has been introduced by Caldarelli et al. Here a link is created between two vertices [math]\displaystyle{ i,j }[/math] with a probability given by a linking function [math]\displaystyle{ f(\eta_i,\eta_j) }[/math] of the fitnesses of the vertices involved. The degree of a vertex i is given by

[math]\displaystyle{ k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j }[/math]

If [math]\displaystyle{ k(\eta_i) }[/math] is an invertible and increasing function of [math]\displaystyle{ \eta_i }[/math], then the probability distribution [math]\displaystyle{ P(k) }[/math] is given by

[math]\displaystyle{ P(k)=\rho(\eta(k)) \cdot \eta'(k) }[/math]

As a result, if the fitnesses [math]\displaystyle{ \eta }[/math] are distributed as a power law, then also the node degree does.

Less intuitively with a fast decaying probability distribution as [math]\displaystyle{ \rho(\eta)=e^{-\eta} }[/math] together with a linking function of the kind

[math]\displaystyle{ f(\eta_i,\eta_j)=\Theta(\eta_i+\eta_j-Z) }[/math]

with [math]\displaystyle{ Z }[/math] a constant and [math]\displaystyle{ \Theta }[/math] the Heavyside function, we also obtain scale-free networks.

Such model has been successfully applied to describe trade between nations by using GDP as fitness for the various nodes [math]\displaystyle{ i,j }[/math] and a linking function of the kind

[math]\displaystyle{ \frac{\delta \eta_i\eta_j}{1+ \delta \eta_i\eta_j}. }[/math]

网络分析 Network analysis

社会网络分析 Social network analysis

Social network analysis examines the structure of relationships between social entities. These entities are often persons, but may also be groups, organizations, nation states, web sites, scholarly publications.

Since the 1970s, the empirical study of networks has played a central role in social science, and many of the mathematical and statistical tools used for studying networks have been first developed in sociology. Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors. Similarly, it has been used to examine the spread of both diseases and health-related behaviors. It has also been applied to the study of markets, where it has been used to examine the role of trust in exchange relationships and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into political movements and social organizations. It has also been used to conceptualize scientific disagreements as well as academic prestige. More recently, network analysis (and its close cousin traffic analysis) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and leaderless nature.In criminology, it is being used to identify influential actors in criminal gangs, offender movements, co-offending, predict criminal activities and make policies.

Social network analysis examines the structure of relationships between social entities.[27] These entities are often persons, but may also be groups, organizations, nation states, web sites, scholarly publications.

Since the 1970s, the empirical study of networks has played a central role in social science, and many of the mathematical and statistical tools used for studying networks have been first developed in sociology.[28] Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors. Similarly, it has been used to examine the spread of both diseases and health-related behaviors. It has also been applied to the study of markets, where it has been used to examine the role of trust in exchange relationships and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into political movements and social organizations. It has also been used to conceptualize scientific disagreements as well as academic prestige. More recently, network analysis (and its close cousin traffic analysis) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and leaderless nature.[29][30]In criminology, it is being used to identify influential actors in criminal gangs, offender movements, co-offending, predict criminal activities and make policies.[31]

社会网络分析考察了社会实体之间的关系结构。 [27]这些实体通常是个人，但也可能是团体、组织、民族国家、网站、学术出版物。

自20世纪70年代以来，对网络的实证研究在21社会科学发挥了核心作用，许多用于研究网络的数学和统计工具最早是在社会学中发展起来的。 [28]在众多的应用中，社会网络分析被用来分析产品创新、新闻和谣言的扩散机制，同时也被用来检测疾病传播和与健康相关的行为。它也被应用于市场研究，主要用于分析信任在交换关系中的作用和社会机制在市场定价中的作用。 同样，它也可以用于研究政治运动和社会组织的招募问题，以及概念化科学分歧和学术声望。 最近，网络分析(及其相近概念流量分析)在军事情报中得到了重要的应用，用于揭露叛乱者网络层级性和无领导性的本质。 在犯罪学中，它也被用来识别犯罪团伙、犯罪运动、共同犯罪以及预测犯罪活动等，从而制定相应的政策。 [31]

Dynamic network analysis

Dynamic network analysis examines the shifting structure of relationships among different classes of entities in complex socio-technical systems effects, and reflects social stability and changes such as the emergence of new groups, topics, and leaders. Dynamic Network Analysis focuses on meta-networks composed of multiple types of nodes (entities) and multiple types of links. These entities can be highly varied. Examples include people, organizations, topics, resources, tasks, events, locations, and beliefs.

Dynamic network techniques are particularly useful for assessing trends and changes in networks over time, identification of emergent leaders, and examining the co-evolution of people and ideas.

Dynamic network analysis examines the shifting structure of relationships among different classes of entities in complex socio-technical systems effects and reflects social stability and changes such as the emergence of new groups, topics, and leaders.[7][8][9][10][32] Dynamic Network Analysis focuses on meta-networks composed of multiple types of nodes (entities) and multiple types of links. These entities can be highly varied.[7] Examples include people, organizations, topics, resources, tasks, events, locations, and beliefs.

Dynamic network techniques are particularly useful for assessing trends and changes in networks over time, identification of emergent leaders, and examining the co-evolution of people and ideas.

动态网络分析考察了在复杂的社会技术系统影响下，不同类别的实体之间关系的转变结构，并反映了社会稳定性以及变化，如新群体、主题和领导者的涌现。 动态网络分析集中于由多种类型的节点(实体)和多种类型的链接组成的元网络。 这些实体可以非常多样化，包括人员、组织、主题、资源、任务、事件、地点甚至是信仰。

动态网络技术是非常有用的一种方法，特别是对于评估网络随时间变化的趋势和变化，识别新兴领导者，以及检查人与想法的共同进化等方面。

Biological network analysis

With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest. The type of analysis in this content are closely related to social network analysis, but often focusing on local patterns in the network. For example, network motifs are small subgraphs that are over-represented in the network. Activity motifs are similar over-represented patterns in the attributes of nodes and edges in the network that are over represented given the network structure. The analysis of biological networks has led to the development of network medicine, which looks at the effect of diseases in the interactome.

With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest. The type of analysis in this content are closely related to social network analysis, but often focusing on local patterns in the network. For example, network motifs are small subgraphs that are over-represented in the network. Activity motifs are similar over-represented patterns in the attributes of nodes and edges in the network that are over represented given the network structure. The analysis of biological networks has led to the development of network medicine, which looks at the effect of diseases in the interactome.[33]

随着近年来公开的生物学数据的爆炸性增长，分子网络的分析引起了人们极大的兴趣。对于生物网络的分析方法与社会网络分析分析密切相关，但通常更关注于网络中的局部模式。例如网络模体network motifs是指网络中一些小的子图；活动图也是指类似的被过度表征的斑图，在给定网络结构下，它们是指在网络中节点和连边的贡献度被过度表示。生物网络的分析促进了网络医学的发展，网络医学主要是从交互中观察疾病的影响。 [33]

18621066378（讨论）motifs找到的相关资料是说：我们说motifs就是与随机网络相比出现次数较多的n-node subgraph结构。那么翻译成中文应该是什么呢？18621066378（讨论）

Link analysis

Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computer-assisted or fully automatic computer-based link analysis is increasingly employed by banks and insurance agencies in fraud detection, by telecommunication operators in telecommunication network analysis, by medical sector in epidemiology and pharmacology, in law enforcement investigations, by search engines for relevance rating (and conversely by the spammers for spamdexing and by business owners for search engine optimization), and everywhere else where relationships between many objects have to be analyzed.

Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computer-assisted or fully automatic computer-based link analysis is increasingly employed by banks and insurance agencies in fraud detection, by telecommunication operators in telecommunication network analysis, by medical sector in epidemiology and pharmacology, in law enforcement investigations, by search engines for relevance rating (and conversely by the spammers for spamdexing and by business owners for search engine optimization), and everywhere else where relationships between many objects have to be analyzed.

链路分析是网络分析的一个子集，主要是探索对象之间的联系。 例如，作为警方调查的一部分，可以分析嫌疑人和受害人的地址、他们所拨打的电话号码和他们在一段时间内参与的金融交易，以及这些对象之间的家庭关系。链路分析提供了许多不同类型的对象之间的关键关系和相互联系，而这些在孤立的信息片段中是看不出来的。计算机辅助或全自动的基于计算机的链接分析越来越多地被银行和保险机构用于欺诈检测，被电信运营商用于电信网络分析，被医疗部门用于流行病学和药理学，被用于执法调查，被用于搜索引擎用于相关性评级(反之亦然，被滥发信息者用于滥发信息，及被业务负责人优化搜索引擎) 以及被用于任何有联系对象之间的分析。

Network robustness

The structural robustness of networks is studied using percolation theory. When a critical fraction of nodes is removed the network becomes fragmented into small clusters. This phenomenon is called percolation and it represents an order-disorder type of phase transition with critical exponents.

The structural robustness of networks[34] is studied using percolation theory. When a critical fraction of nodes is removed the network becomes fragmented into small clusters. This phenomenon is called percolation[35] and it represents an order-disorder type of phase transition with critical exponents.

利用渗流理论研究了网络[34]的结构鲁棒性。 当节点的一个临界部分被移除时，网络变得支离破碎。 这种现象被称为渗流[35] ，它代表了一种从有序-无序的临界指数的相变类型。

Pandemic analysis

流行病分析

The SIR model is one of the most well known algorithms on predicting the spread of global pandemics within an infectious population.

The SIR model is one of the most well known algorithms on predicting the spread of global pandemics within an infectious population.

SIR模型是预测全球传染病在感染人群中传播的最著名的算法之一。

Susceptible to infected

易感人群

[math]\displaystyle{ S = \beta\left(\frac 1 N \right) }[/math]

The formula above describes the "force" of infection for each susceptible unit in an infectious population, where β is equivalent to the transmission rate of said disease.

这个公式描述的是人群中每个易感单元的感染“力”，其中 β 代表的是疾病的传播概率。

To track the change of those susceptible in an infectious population: 跟踪人群中易感人数随时间的变化：

[math]\displaystyle{ \Delta S = \beta \times S {1\over N} \, \Delta t }[/math]

Infected to recovered

感染到康复

[math]\displaystyle{ \Delta I = \mu I \, \Delta t }[/math]

Over time, the number of those infected fluctuates by: the specified rate of recovery, represented by [math]\displaystyle{ \mu }[/math] but deducted to one over the average infectious period [math]\displaystyle{ {1\over \tau} }[/math], the numbered of infectious individuals, [math]\displaystyle{ I }[/math], and the change in time, [math]\displaystyle{ \Delta t }[/math].

随着时间的推移，感染人数的波动幅度为: 以[math]\displaystyle{ \mu }[/math]来表示特定的恢复率，移除的平均感染期记为[math]\displaystyle{ {1\over \tau} }[/math]，感染个体的数量 [math]\displaystyle{ I }[/math]，以及时间的变化[math]\displaystyle{ \Delta t }[/math]。

Infectious period

感染时期

Whether a population will be overcome by a pandemic, with regards to the SIR model, is dependent on the value of [math]\displaystyle{ R_0 }[/math] or the "average people infected by an infected individual." 就 SIR 模型而言，被流行病感染的人口数量，取决于数学[math]\displaystyle{ R_0 }[/math]基本传染数的数值，是指被感染个体能感染普通人群的人数。比如[math]\displaystyle{ R_0 = 3 }[/math]，意味着一个感染者平均感染3个未感染者。

[math]\displaystyle{ R_0 = \beta\tau = {\beta\over\mu} }[/math]

Web link analysis

网络连接分析

Several Web search ranking algorithms use link-based centrality metrics, including (in order of appearance) Marchiori's Hyper Search, Google's PageRank, Kleinberg's HITS algorithm, the CheiRank and TrustRank algorithms. Link analysis is also conducted in information science and communication science in order to understand and extract information from the structure of collections of web pages. For example, the analysis might be of the interlinking between politicians' web sites or blogs.

Several Web search ranking algorithms use link-based centrality metrics, including (in order of appearance) Marchiori's Hyper Search, Google's PageRank, Kleinberg's HITS algorithm, the CheiRank and TrustRank algorithms. Link analysis is also conducted in information science and communication science in order to understand and extract information from the structure of collections of web pages. For example, the analysis might be of the interlinking between politicians' web sites or blogs. 一些网络搜索排名算法使用基于链接的中心度矩阵，包括Marchiori的 Hyper Search、 Google 的 PageRank、 Kleinberg 的 HITS 算法、 CheiRank 和 TrustRank 算法。 在信息科学和传播学中也进行链接分析，以便从网页的结构中理解和提取信息。 例如，可以分析政客的网站或博客之间的相互联系。

思无涯咿呀咿呀（讨论）link-based centrality metrics思无涯咿呀咿呀（讨论）

PageRank

PageRank works by randomly picking "nodes" or websites and then with a certain probability, "randomly jumping" to other nodes. By randomly jumping to these other nodes, it helps PageRank completely traverse the network as some webpages exist on the periphery and would not as readily be assessed.

PageRank works by randomly picking "nodes" or websites and then with a certain probability, "randomly jumping" to other nodes. By randomly jumping to these other nodes, it helps PageRank completely traverse the network as some webpages exist on the periphery and would not as readily be assessed.

Each node, [math]\displaystyle{ x_i }[/math], has a PageRank as defined by the sum of pages [math]\displaystyle{ j }[/math] that link to [math]\displaystyle{ i }[/math] times one over the outlinks or "out-degree" of [math]\displaystyle{ j }[/math] times the "importance" or PageRank of [math]\displaystyle{ j }[/math].

PageRank算法的工作原理是随机选择“节点”或网站，然后以一定的概率“随机跳转”到其他节点。 通过随机跳转到这些其他节点，它帮助 PageRank算法完全遍历网络，因为可能一些不容易被跳转到的边缘网站。

[math]\displaystyle{ x_i = \sum_{j\rightarrow i}{1\over N_j}x_j^{(k)} }[/math]

Random jumping

随机跳转 As explained above, PageRank enlists random jumps in attempts to assign PageRank to every website on the internet. These random jumps find websites that might not be found during the normal search methodologies such as Breadth-First Search and Depth-First Search. 正如上面解释的那样，试图通过随机跳转，为互联网上的每个网站分配网页排名。通过随机跳转可以找到一些在正常的搜索方法（如广度优先搜索和深度优先搜索）中找不到的边缘网站。

In an improvement over the aforementioned formula for determining PageRank includes adding these random jump components. Without the random jumps, some pages would receive a PageRank of 0 which would not be good.

在上述公式中，该算法的主要提升是添加了随机跳转，没有这些随机跳转，一些网页的排名可能就是0，这样是非常不好的。

The first is [math]\displaystyle{ \alpha }[/math], or the probability that a random jump will occur. Contrasting is the "damping factor", or [math]\displaystyle{ 1 - \alpha }[/math]. 第一个字母[math]\displaystyle{ \alpha }[/math]，代表的是随机跳转发生的概率。与此相对的是阻尼因子，对应的是[math]\displaystyle{ 1 - \alpha }[/math]。

[math]\displaystyle{ R{(p)} = {\alpha\over N} + (1 - \alpha) \sum_{j\rightarrow i} {1\over N_j} x_j^{(k)} }[/math]

Another way of looking at it: 从另一个角度来看

[math]\displaystyle{ R(A) = \sum {R_B\over B_\text{(outlinks)}} + \cdots + {R_n \over n_\text{(outlinks)}} }[/math]

Centrality measures

中心性度量

Information about the relative importance of nodes and edges in a graph can be obtained through centrality measures, widely used in disciplines like sociology. Centrality measures are essential when a network analysis has to answer questions such as: "Which nodes in the network should be targeted to ensure that a message or information spreads to all or most nodes in the network?" or conversely, "Which nodes should be targeted to curtail the spread of a disease?". Formally established measures of centrality are degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, and katz centrality. The objective of network analysis generally determines the type of centrality measure(s) to be used.

• Degree centrality of a node in a network is the number of links (vertices) incident on the node.
• 度中心性是指网络中节点的

• Closeness centrality determines how "close" a node is to other nodes in a network by measuring the sum of the shortest distances (geodesic paths) between that node and all other nodes in the network.
• Betweenness centrality determines the relative importance of a node by measuring the amount of traffic flowing through that node to other nodes in the network. This is done by measuring the fraction of paths connecting all pairs of nodes and containing the node of interest. Group Betweenness centrality measures the amount of traffic flowing through a group of nodes.
• Eigenvector centrality is a more sophisticated version of degree centrality where the centrality of a node not only depends on the number of links incident on the node but also the quality of those links. This quality factor is determined by the eigenvectors of the adjacency matrix of the network.
• Katz centrality of a node is measured by summing the geodesic paths between that node and all (reachable) nodes in the network. These paths are weighted, paths connecting the node with its immediate neighbors carry higher weights than those which connect with nodes farther away from the immediate neighbors.

Spread of content in networks

Content in a complex network can spread via two major methods: conserved spread and non-conserved spread. In conserved spread, the total amount of content that enters a complex network remains constant as it passes through. The model of conserved spread can best be represented by a pitcher containing a fixed amount of water being poured into a series of funnels connected by tubes. Here, the pitcher represents the original source and the water is the content being spread. The funnels and connecting tubing represent the nodes and the connections between nodes, respectively. As the water passes from one funnel into another, the water disappears instantly from the funnel that was previously exposed to the water. In non-conserved spread, the amount of content changes as it enters and passes through a complex network. The model of non-conserved spread can best be represented by a continuously running faucet running through a series of funnels connected by tubes. Here, the amount of water from the original source is infinite. Also, any funnels that have been exposed to the water continue to experience the water even as it passes into successive funnels. The non-conserved model is the most suitable for explaining the transmission of most infectious diseases.

The SIR model

In 1927, W. O. Kermack and A. G. McKendrick created a model in which they considered a fixed population with only three compartments, susceptible: [math]\displaystyle{ S(t) }[/math], infected, [math]\displaystyle{ I(t) }[/math], and recovered, [math]\displaystyle{ R(t) }[/math]. The compartments used for this model consist of three classes:

• [math]\displaystyle{ S(t) }[/math] is used to represent the number of individuals not yet infected with the disease at time t, or those susceptible to the disease
• [math]\displaystyle{ I(t) }[/math] denotes the number of individuals who have been infected with the disease and are capable of spreading the disease to those in the susceptible category
• [math]\displaystyle{ R(t) }[/math] is the compartment used for those individuals who have been infected and then recovered from the disease. Those in this category are not able to be infected again or to transmit the infection to others.

The flow of this model may be considered as follows:

[math]\displaystyle{ \mathcal{S} \rightarrow \mathcal{I} \rightarrow \mathcal{R} }[/math]

Using a fixed population, [math]\displaystyle{ N = S(t) + I(t) + R(t) }[/math], Kermack and McKendrick derived the following equations:

[math]\displaystyle{ \begin{align} \frac{dS}{dt} & = - \beta S I \\[8pt] \frac{dI}{dt} & = \beta S I - \gamma I \\[8pt] \frac{dR}{dt} & = \gamma I \end{align} }[/math]

Several assumptions were made in the formulation of these equations: First, an individual in the population must be considered as having an equal probability as every other individual of contracting the disease with a rate of [math]\displaystyle{ \beta }[/math], which is considered the contact or infection rate of the disease. Therefore, an infected individual makes contact and is able to transmit the disease with [math]\displaystyle{ \beta N }[/math] others per unit time and the fraction of contacts by an infected with a susceptible is [math]\displaystyle{ S/N }[/math]. The number of new infections in unit time per infective then is [math]\displaystyle{ \beta N (S/N) }[/math], giving the rate of new infections (or those leaving the susceptible category) as [math]\displaystyle{ \beta N (S/N)I = \beta SI }[/math] (Brauer & Castillo-Chavez, 2001). For the second and third equations, consider the population leaving the susceptible class as equal to the number entering the infected class. However, infectives are leaving this class per unit time to enter the recovered/removed class at a rate [math]\displaystyle{ \gamma }[/math] per unit time (where [math]\displaystyle{ \gamma }[/math] represents the mean recovery rate, or [math]\displaystyle{ 1/\gamma }[/math] the mean infective period). These processes which occur simultaneously are referred to as the Law of Mass Action, a widely accepted idea that the rate of contact between two groups in a population is proportional to the size of each of the groups concerned (Daley & Gani, 2005). Finally, it is assumed that the rate of infection and recovery is much faster than the time scale of births and deaths and therefore, these factors are ignored in this model.

More can be read on this model on the Epidemic model page.

The master equation approach

A master equation can express the behaviour of an undirected growing network where, at each time step, a new node is added to the network, linked to an old node (randomly chosen and without preference). The initial network is formed by two nodes and two links between them at time [math]\displaystyle{ t = 2 }[/math], this configuration is necessary only to simplify further calculations, so at time [math]\displaystyle{ t = n }[/math] the network have [math]\displaystyle{ n }[/math] nodes and [math]\displaystyle{ n }[/math] links.

The master equation for this network is:

[math]\displaystyle{ p(k,s,t+1) = \frac 1 t p(k-1,s,t) + \left(1 - \frac 1 t \right)p(k,s,t), }[/math]

where [math]\displaystyle{ p(k,s,t) }[/math] is the probability to have the node [math]\displaystyle{ s }[/math] with degree [math]\displaystyle{ k }[/math] at time [math]\displaystyle{ t+1 }[/math], and [math]\displaystyle{ s }[/math] is the time step when this node was added to the network. Note that there are only two ways for an old node [math]\displaystyle{ s }[/math] to have [math]\displaystyle{ k }[/math] links at time [math]\displaystyle{ t+1 }[/math]:

• The node [math]\displaystyle{ s }[/math] have degree [math]\displaystyle{ k-1 }[/math] at time [math]\displaystyle{ t }[/math] and will be linked by the new node with probability [math]\displaystyle{ 1/t }[/math]
• Already has degree [math]\displaystyle{ k }[/math] at time [math]\displaystyle{ t }[/math] and will not be linked by the new node.

After simplifying this model, the degree distribution is [math]\displaystyle{ P(k) = 2^{-k}. }[/math]

Based on this growing network, an epidemic model is developed following a simple rule: Each time the new node is added and after choosing the old node to link, a decision is made: whether or not this new node will be infected. The master equation for this epidemic model is:

[math]\displaystyle{ p_r(k,s,t) = r_t \frac 1 t p_r(k-1,s,t) + \left(1 - \frac 1 t \right) p_r(k,s,t), }[/math]

where [math]\displaystyle{ r_t }[/math] represents the decision to infect ([math]\displaystyle{ r_t = 1 }[/math]) or not ([math]\displaystyle{ r_t = 0 }[/math]). Solving this master equation, the following solution is obtained: [math]\displaystyle{ \tilde{P}_r(k) = \left(\frac r 2 \right)^k. }[/math]

Interdependent networks

Main article: Interdependent networks

An interdependent network is a system of coupled networks where nodes of one or more networks depend on nodes in other networks. Such dependencies are enhanced by the developments in modern technology. Dependencies may lead to cascading failures between the networks and a relatively small failure can lead to a catastrophic breakdown of the system. Blackouts are a fascinating demonstration of the important role played by the dependencies between networks. A recent study developed a framework to study the cascading failures in an interdependent networks system.

Multilayer networks

Main article: Multidimensional network

Multilayer networks are networks with multiple kinds of relations. Attempts to model real-world systems as multidimensional networks have been used in various fields such as social network analysis, economics, history, urban and international transport, ecology, psychology, medicine, biology, commerce, climatology, physics, computational neuroscience, operations management, and finance.

Network optimization

Network problems that involve finding an optimal way of doing something are studied under the name of combinatorial optimization. Examples include network flow, shortest path problem, transport problem, transshipment problem, location problem, matching problem, assignment problem, packing problem, routing problem, Critical Path Analysis and PERT (Program Evaluation & Review Technique).

See also

• Climate as complex networks
• Collaborative innovation network
• Communicative ecology
• Complex network
• Core-periphery structures in networks
• Dual-phase evolution
• Erdős–Rényi model
• Glossary of graph theory
• Higher category theory
• Immune network theory
• Irregular warfare
• Network analyzer
• Network dynamics
• Network formation
• Network theory in risk assessment
• Network topology
• Networks in labor economics
• Non-linear preferential attachment
• Percolation
• Policy network analysis
• Polytely
• Quantum complex network
• Random networks
• Rumor spread in social network
• Scale-free networks
• Sequential dynamical system
• Service network
• Small-world networks
• Structural cut-off
• Systems theory

Further reading

• "Connected: The Power of Six Degrees," https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• Cohen, R.; Erez, K.; Havlin, S. (2000). "Resilience of the Internet to random breakdown". Phys. Rev. Lett. 85 (21): 4626–4628. arXiv:cond-mat/0007048. Bibcode:2000PhRvL..85.4626C. CiteSeerX 10.1.1.242.6797. doi:10.1103/physrevlett.85.4626. PMID 11082612.
• Pu, Cun-Lai; Wen-; Pei, Jiang; Michaelson, Andrew (2012). "Robustness analysis of network controllability" (PDF). Physica A. 391 (18): 4420–4425. Bibcode:2012PhyA..391.4420P. doi:10.1016/j.physa.2012.04.019. Archived from the original (PDF) on 2016-10-13. Retrieved 2013-09-18.
• "Leader Profile: The Burgeoning Field of Network Science, The Military Engineer recently had the opportunity to speak with Frederick I. Moxley, Ph.D," https://web.archive.org/web/20190215025457/http://themilitaryengineer.com/index.php/item/160-leader-profile-the-burgeoning-field-of-network-science
• S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW, Oxford University Press, 2003,
  • Linked: The New Science of Networks, A.-L. Barabási (Perseus Publishing, Cambridge)
  • 'Scale-Free Networks, G. Caldarelli (Oxford University Press, Oxford)
  • Network Science, Committee on Network Science for Future Army Applications, National Research Council. 2005. The National Academies Press (2005)
    • Network Science Bulletin, USMA (2007)
      • The Structure and Dynamics of Networks Mark Newman, Albert-László Barabási, & Duncan J. Watts (The Princeton Press, 2006)
        • Dynamical processes on complex networks, Alain Barrat, Marc Barthelemy, Alessandro Vespignani (Cambridge University Press, 2008)
          • Network Science: Theory and Applications, Ted G. Lewis (Wiley, March 11, 2009)
            • Nexus: Small Worlds and the Groundbreaking Theory of Networks, Mark Buchanan (W. W. Norton & Company, June 2003)
              • Six Degrees: The Science of a Connected Age, Duncan J. Watts (W. W. Norton & Company, February 17, 2004)
                • Kitsak, M.; Gallos, L. K.; Havlin, S.; Liljeros, F.; Muchnik, L.; Stanley, H. E.; Makse, H.A. (2010). "Influential Spreaders in Networks". Nature Physics. 6 (11): 888–893. arXiv:1001.5285. Bibcode:2010NatPh...6..888K. CiteSeerX 10.1.1.366.2543. doi:10.1038/nphys1746.