英语原文共 62 页，剩余内容已隐藏，支付完成后下载完整资料
复杂网络中随机游走示意图揭示社团结构
摘要
为了理解大规模生物学和社会学系统的多部分组织结构，我们引入一种信息论方法，该方法揭示了加权有向网络的社团结构。我们用在网络中随机游走的概率流代表真实系统中的信息流，并且通过简化概率流的描述将网络分解为各个模块。产生的结果是一种同时简化和突出结构上的规律性和各模块之间关系的示意图。我们在超过6000个杂志的引用形式中提取产生了一幅科学交流示意图，由此阐述了该方法。我们发现了一个多中心的组织结构，它的各个领域在规模上和在科学网络的整合程度上都有很大的不同。顺着网络主干——包括物理学、化学、分子生物学和药学——信息双向流动，但是该示意图揭示了从应用领域到基础科学的引文有向性模式。
关键词：聚类；压缩；信息论；科学示意图；文献计量学
生物和社会系统是有区别的、多部分的、综合的和动态的。关于这些系统以前所未有的规模提供的数据，经常被图示化为网络。这样的抽象是强有力的（1, 2），但即使是抽象的概念，它们仍然是高度复杂的。因此，将大量的节点和连边分解为能够表示整个网络的模块是很有帮助的（3-5）。一个有说服力的表示将保留关于网络的重要信息，并反映出这样一个事实：复杂系统中元素之间的相互作用是加权、有向、相互依赖和可传导的。一个良好的表示同时简化和突出了基础结构和它们所描述的关系；它们是示意图（6, 7）。
为了创建一幅良好的示意图，制图者必须在忽略重要结构的同时，通过过分简化和在大量多余的细节中隐藏重要的关系来达到一个很好的平衡。最佳的示意图能传达大量信息，但却需要最小的带宽：最佳的示意图也是对信息的良好的压缩。通过采用信息理论的方法，我们可以测量示意图代表潜在布局的效率，可以测量在简化过程中丢失了多少细节，这使得我们能够量化和解决制图者的取舍。
1.网络示意图和编码理论
在本文中，我们使用示意图来描述在有向的、加权的网络中跨连边和节点的动力学，这些网络表示系统的子单元之间的局部交互。这些局部交互引起了系统范围内的信息流动，信息流动描述了整个系统的行为（8-12）。因此，如果我们想要了解网络结构与系统行为的关系，我们就需要了解网络上的信息流。因此，我们通过找到对网络上信息流动的有效粗粒度描述来识别组成网络的模块。若有一组信息可以在其中快速且容易流动的节点，那么这组节点可以聚合在一起，并将其描述为单个连接良好的模块；模块之间的连接捕获了这些模块之间的信息流的途径。
简洁地描述信息流是一个编码或压缩问题。编码理论的关键思想是，数据流可以通过利用产生流的过程中的规则来压缩（13）。我们使用随机游走代表信息流，因为随机游走使用网络表示中的所有信息，仅此而已。因此，它提供了一种默认机制，可以仅从网络示意图中产生动态（8）。
采用这种方法，我们开发了一种有效的代码来描述网络上的随机游走。进而我们展示了在网络中寻找社团结构等价于解决编码问题（14-16）。我们通过构造一张科学示意图，来举例说明这个方法，它基于科学期刊上通过引用产生的信息流。
1.1 描述网络上的路径
为了说明编码与示意图制作有什么关系，考虑下面的通信游戏。假设你和我都知道加权有向网络的结构。我们的目标是选择一种代码，使我们能够有效地用一种语言描述网络上的路径，这些路径来自于一个反映网络底层结构的语言的随机游走过程。我们应该如何设计代码?
如果最大压缩是我们唯一的目标，我们可以在达到或接近相应的马尔可夫过程的熵速率的情况下对路径进行编码。香农表明，可以通过向每个节点分配一个独立的字典通过向外转换来达到这个速率（17）。但压缩不是我们唯一的目标。这里，我们想让我们的语言反映网络结构，我们想让我们使用的词汇适用于世界上的事物。香农的方法并不适用于我们，因为每个字码都有不同的意思，这取决于它们用在何处。比较这些示意图：有用的示意图为重要的结构分配唯一的名称。因此，我们寻求一种描述或编码随机游走的方法，其中重要的结构确实保留着独特的名称。让我们来看一个具体的例子。图1A展示的是一个具有n=25个节点的加权网络。链路的粗细程度表明随机游走会穿过任意特定连边的相对概率。覆盖在网络上的是一个特定的71步随机游走的实现，我们将用它来说明我们的通信游戏。在图1中，我们描述了随着压缩级别的增加(B-D)，利用网络中越来越多的规则。
1.2 哈夫曼编码
给节点命名的一种简单方法是使用哈夫曼编码（18）。哈夫曼编码通过将短字码分配给公共事件或对象，并将长字码分配给罕见的事件或对象，来节省空间，这就跟口语中的常用字都很短一样。图1B展示了样本网络的无前缀哈夫曼编码。每个字码指定一个特定的节点，而字码长度则来自于一个无限长的随机游走的遍历节点访问频率。用图1B中的哈夫曼编码，我们可以用314比特数据描述具体的71步游走。如果我们选择了一个统一的编码，其中所有的字码长度相等，那么每个字码将是比特长，需要71*5=355比特数据来描述游走。虽然在这个示例中，我们将实际的代码字分配给节点以进行说明，但一般来说，我们感兴趣的不是字码本身，而是能够以理论上的极限精确地指定路径。在这里，我们引用香农的信源编码定理(17)，即当你使用n个字码来描述一个随机变量X的n个状态（每个状态的频率为）时，字码的平均长度不小于随机变量X本身的熵：。这个定理为我们提供了必要的工具，在我们的哈夫曼图示中，描述随机游走中的单步所需的平均位数被限制在熵H(P)之下，其中P是网络上节点访问频率的分布。我们定义字码长度下界为L，例如，图1B中每一步的L =4.50比特。
1.3 突出重要的对象
将字码长度与使用频率相匹配，可以为节点提供有效的字码，但没有示意图。仅仅为节点分配适当长度的名称对于简化或突出底层结构的各个层面没有多大作用。为了绘制示意图，我们需要将重要的结构与无关紧要的细节分开。因此，我们将网络划分为两个层次的描述。对于网络中大型对象、集群或模块，我们保留唯一名称，但是我们重复使用了与细粒度细节相关的名称，也就是每个模块中的各个节点的字码。这是在地图上为对象分配名称的常用方法：大多数美国城市都有唯一的名字，但不同城市街道名都是重复使用的，这样每个城市都有一条主干道，一条百老汇大街和一条华盛顿大道，等等。街道名的重复使用几乎不会引起混乱，因为大多数路线都是在一个城市的范围内。
二级描述允许我们用比一级描述更少的比特来描述路径。我们利用了网络的结构，特别的是，一个随机游走在统计上很可能长时间在特定的节点群集内。图1C说明了这种方法。我们给每个集群唯一的名称，但是使用不同的哈夫曼编码来命名每个集群中的节点。一个特殊的字码，即退出码，被选为哈夫曼编码内的一部分，并表示游走将要离开当前的集群。退出码后面总是会有游走将要移入的新的模块“名称”或模块码[有关更多细节，请参见支持信息(SI)]。因此，我们为粗粒结构(城市隐喻中的城市)分配了唯一的名称，但是重复使用与细粒度细节相关的名称(城市隐喻中的街道)。节约了相当大的空间；在图C的二级描述中，每一步游走的L下限是3.05比特，而在一级描述中是4.50比特。
这里，在网络中寻找社团结构和编码问题之间存在着二元性:为了找到一个有效的编码，我们寻找一个将n个节点划分到m个模块的模块划分M，从而使得随机游走的预期描述长度最小化。利用模块划分M，单个步骤的平均描述长度由下面的式子给出：
该方程由两项组成:一是模块之间的运动熵，二是模块内运动的熵(其中离开模块也考虑为一次运动)。每一项都是按其在特定分区中发生的频率加权的。这里
是任意给定的走步中随机游走转换模块的概率。是模块名的熵,换言之，是图1D中下划线字码的熵。是指在模块内部运动的熵，包括模块i的退出码。权重是发生在模块i中的模块内部运动的百分比，加上退出模块i的概率，使得（参见SI了解更多细节）。
对于所有网络（除了最小的网络之外），检查所有可能的划分来寻找示意图方程（等式1）中的最小化描述长度的划分是不可行的。相反地，我们使用计算搜索。我们首先使用幂函数方法计算通过随机游走访问每个节点的次数的百分比，并利用这些访问频率，通过使用确定性的贪婪搜索算法（20，21）来探索可能的划分空间。我们使用热浴算法对结果进行了模拟退火(6)优化（参见SI了解更多细节）。
图1D显示了网络的示意图，其中模块内部的描述字码逐渐消失；这里突出显示了重要的对象，细节已经被过滤掉了。为了看起来简单，图1中的说明性网络是加权无向的。我们的方法得到了更一般化的拓展，由此我们可以从加权有向网络中提取信息。示意图方程保持不变；只有稍微修改我们想要描述的路径才能实现遍历性。我们在随机游走中引入了一个小的“传送概率”tau;。在概率tau;的作用下，随机游走会跳转到网络中的任意一个节点，它将我们的随机游走者转换成驱动谷歌的PageRank算法（22）的“随机冲浪者”。我们的聚类结果对tau;的特定选择具有很强的鲁棒性。例如，只要tau;lt;0.45，图1中网络的最优划分仍然是完全相同的。我们选择tau;=0.15对应于PageRank算法中著名的阻尼因子d =0.85(22)。
2. 与最大化模块度相比的示意图流动
在加权有向网络中传统的社团结构识别方法，仅仅是忽略了连边的方向和权重。但是这种方法丢失了关于网络结构的宝贵信息。通过描绘由节点之间的局部交互引起的系统范围的信息流，我们保留了关于连边方向和权重的信息。我们也承认它们在网络固有的流动特征中相互依存。这一特性使得将基于信息流的方法与同样利用了权重和方向信息的基于模块度优化（23-26）的最新拓扑方法进行比较变得很有趣。在最一般的形式中，将网络划分为m个模块的模块是每个模块中所有连边的总权重减去期望权重的总和：
这里，是在模块i中起始和终止的连边的总权重，和是模块i中连边的总入权和总出权，w是网络中所有连边的总权。为了估计网络中的社团结构，在所有可能的节点分配中，等式2被最大化为m个模块。等式1和2反映了网络的两种不同的含义。我们在这里所研究的前者，发现了网络在其结构所导致的流动模式中的本质。后者有效地将网络的本质置于其连接的拓扑属性中（正如我们在引文16中所做的）。
这种概念上的区别有什么实际影响吗? 图2说明了两个简单的网络，其中示意图方程和模块度给出了不同的划分。图2A中所示的加权有向连边导致了一种结构化的信息流模式，它具有在模块内部较长的持续时间和模块之间有限的流量，这四个集群在左边突出显示。示意图方程对这些结构规律进行了分析，因此，图2A左边（每步2.67比特）比图2A右边(每步4.13位)的描述长度要短得多。模块度很难理解以流动为特征的网络中的相互依赖，因此不能揭示这种结构的规律性。它只计算模块中的边权、入度和出度，因此更倾向于划分如图2A右图所示的网络，其中权重较大的连边包含在模块内部。
相反地，在图2B中，根本没有扩展信息流的模式。每个节点要么是一个源节点，要么是一个汇聚点，并且网络上的连边上没有任何移动可以超过一步以上的长度。因此，随机传送将占主导地位(不考虑传送率)，任何分割成多个模块的划分将导致模块间的高流量。对于像图2B这样的连边不会产生信息流模式的网络， 示意图方程总是将网络划分为单个模块。因为模块度关注的是连边、入度和出度的模式，所以将网络划分为如右图所示的集群。
研究人员应该使用哪种方法? 这取决于上面描述的两种方法中的哪一种使研究人员正在研究的网络有意义。为了分析连边表示节点之间的移动模式的网络数据，基于信息流的方法(如示意图方程)可能会识别网络结构最重要的层面。为了分析网络数据，网络中连接不是流动的，而是成对的关系，即使在没有信息流存在的情况下，检测网络结构可能是有用的。对于这些系统，拓扑方法如模块度(11)或基于集群的压缩(16)可能更好。
3. 绘制科学交流图
科学就是一种有高度组织水平和有相同学术水平的人类去发现自然界模式的尝试；交流研究成果的过程对于科学进展来说是至关重要的，正如首先进行研究的行为一样。因此，科学不仅是一系列思想，而且还是一系列通过一个多部分和高度分化的社会系统来实现流动的思想。期刊上的引文模式让我们得以瞥见这种流动，并提供科学家之间交流的痕迹（27-31）。为了突出重要的领域和他们的关系，揭示差异和变化，简化系统以使系统易于理解——我们需要一个好的科学示意图。
利用上述的信息论方法，我们在科学(图3)和社会科学(图4)的6128个期刊之中绘制了引文的流向图。在这个交叉引用网络中，6,434,916个引用代表了2004年(32)的科学活动的痕迹。我们的数据记录在一份期刊的基础上，从2004年发表的文章引用到前5年发表的文章引用。我们排除了每年发表lt;12篇文章的期刊和那些在数据集中不引用其他期刊的期刊。我们还排除了涵盖科学、自然和国家科学院院刊等科学学科范围广泛的三种主要期刊；另外，这些期刊的广泛范围，造成了一种学科之间更紧密联系的错觉，事实上，在科学领域的物理学文章的读者中，几乎没有人是生物医学文章的密切读者。因为我们对期刊之间的关系感兴趣，所以也排除了期刊自我引用。
通过我们算法的操作，领域和它们之间的边界直接从引文数据中出现，而不是从我们预想的科学分类学概念出现（见图3和图4）。我们唯一的主观贡献是为算法识别出的每一组期刊提供了合理的名称，该算法识别出了经济学、数学、地球科学等等。
在图上每个模块或“领域”的物理大小反映了一个随机冲浪者在该模块内所花费的时间的一小部分。字段大小差别很大。分子生物学包括723个期刊，涵盖遗传学、细胞生物学、生物化学、免疫学和发育生物学等领域；一个随机冲浪者花费26%的时间在这个领域，用模块的大小表示。摩擦学(关于摩擦力的研究)只包括7种期刊，随机冲浪者在其中花费0.064%的时间。
领域之间的加权和有向连边表示引用流，箭头的颜色和宽度表示流量。医学和分子生物学之间的巨大箭头表明，这些学科之间存在大量的引用。箭头指向引用的方向：A→B意为“A引用B”如图所示。这些有向的连边揭示了应用和基础科学之间的关系。我们发现前者广泛地引用后者，
全文共6758字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14497]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
