面向动态过程的空间社会复杂网络建模

摘要

社交网络的研究 - 人们所在的地方，地理位置，以及它们如何相互连接 - 是目前兴趣的热门话题，因为它与重要应用的立即相关，从设计有效的免疫技术，以防止流行病为了了解更好的运输和城市规划范式，以了解如何随着时间的推移传播和意见如何传播和形成。We develop a Spatial Social Complex Network (SSCN) model that captures not only essential connectivity features of real-life social networks, including a heavy-tailed degree distribution and high clustering, but also the spatial location of individuals, reproducing Zipf’s law for the distribution of city populations as well as other observed hallmarks. We then simulate Milgram’s Small-World experiment on our SSCN model, obtaining good qualitative agreement with the known results and shedding light on the role played by various network attributes and the strategies used by the players in the game. This demonstrates the potential of the SSCN model for the simulation and study of the many social processes mentioned above, where both connectivity and geography play a role in the dynamics.

1.介绍

近年来，近年来，在大型人口中，在城市，全国，甚至全世界甚至全世界，近年来，近年来近年来一直致力于大量动态过程。例子包括逮捕蔓延的流行病和策略[1-3.]选举中选举地图的演变[4.[谣言的传播[5.]，模因[6.那7.，以及意见[8.]，钞票的迁移模式[9.]人类人口[10.]以及城市和基础设施布局对商业和生产力的影响[11.那12.］．很多问题都需要对个人的地理位置以及他们的社会联系(许多传染病通过直接接触或身体接触传播;我们讨论和影响大多数与我们亲近的人的观点，等等)。

在米尔格拉姆的小世界实验中[13.例如，被要求参与者将消息（明信片）传递给披露的地址，但只能通过社会熟人的链：每个参与者被允许仅将消息传递给他们第一个人所知道的人- 名称。160条消息始于奥马哈，内布拉斯加州，44，或约 那达到了马萨诸塞州波士顿的目标，平均路径长度约为5.4个链接。信息是如何找到它的方式，更不用说在这么短的步骤!?

Kleinberg的精美工作[14.那15.]，对于具有随机远程连接的方形晶格中的节点，提供了第一线索。这后来延伸到分形[16.]和各向异性[17.然而，除了典型的人类社会的地理传播和连接网络中，格子仍然是一个远远令人哭声。Rybski等。最近开发了一个城市的空间增长模型，但这种模型（和其他相关研究中的类似研究）不会捕获社会交互网络[18.］．Dodds等人进行了一个大规模的在线实验，类似于米尔格拉姆最初的研究，突出了信息的作用，而不仅仅是网络结构[19.］．Liben-Nowell等．[20.[]提出了一个空间社交网络模型，该模型基于一个在线博客社区的连接，并在该模型上研究了贪婪路由。对在线社交网络也进行了类似的研究[21.]和社区结构，以流动电话记录[22.那23.](见[24.那25.]以作更全面的回顾)。关于人们的位置及其社会联系的信息通常很难获得，通常依赖于间接代理。

在 [26.我们介绍了一个随机原型空间社交复杂网络（SSCN），依赖于两个可控参数，这些参数模拟了大群体，包括代理之间的位置和复杂的联系人网络。这本“基线模型”是以谦虚的目标设计的：（a）人口密度类似于夜间地球卫星图片中观察到的光密度，（b）“城市”的群体（由渗滤群定义[27.)，它们的排名遵循齐普夫定律[28.-30.③社会联系网络呈无标度分布;④高连接节点倾向于分布在人口密度大的地区。除了满足这些基本目标SSCN基线模型也取得了良好的人口密度与人口普查数据定性协议作为城市大小的函数,和弱的用户依赖的累积程度的节点城市的总人口,建议从手机数据(12.］．最后，它让我们在弱势偏差上揭示了一些光线[27.]来自Gibrat的法律（城市的增长率及其波动与其人口规模成比例）。

尽管有这些初步成功，但SSCN基线模型无法以某种关键方式模仿真实的SSCN：（i）社会联系人的复杂网络，同时展示自由度的无尺度分布，实际上是一个树，而在社会网络及其代理中观察到的高度聚类。(ii)通过重定向机制建立联系网络[31.-33.]，这是对个人如何加入社交网络的充分描述，但未能考虑效果重新搬迁由于学习、工作或其他原因，人们经常会搬迁到一个遥远的地方。这在社会联系网络中产生了特殊的相关性，而这在基线SSCN中是不存在的。

在本文中，我们解决了基线SSCN缺陷，具有一些简单的调整。添加到空间最接近邻居的连接以模仿真实社交网络中的聚类效果，并且重新定位在降低节点之间的平均路径长度时对映射至关重要。Milgram的模拟在修订的SSCN模型上的小世界实验实现了与实证发现的良好定性拟合。这证明了模型作为用于模拟其他动态社交过程的基板的适用性，这取决于代理的触点和地理位置。

2.材料和方法

２.１.基线SSCN模型

我们现在审查原始或“基线”SSCN模型，在我们以前的工作中成立[26.］．该模型生成了一个空间嵌入式网络 在哪里 是一组节点和 是一组无向边。网络的空间嵌入被编码在坐标集合中 ，对于2D空间网络(如我们的例子) ．该模型的一个独特之处在于，它不仅为边缘生成了必要的无尺度度分布，而且还捕获了基本的空间特征，例如从节点聚集到“城市”的人口的Zipf分布[26.］．

考虑首先在基线模型中创建节点和边缘，定义和 ．起点是一个初始的“种子”网络，在基线模型中，它通常由单个节点组成。根据Krapivsky-Redner (KR)模型的一种变体，每次一个节点被添加到网络中，每个节点都贡献一个新边[31.-33.]有一个参数 ——重定向概率．每次一个新节点加入网络，一个现有的节点， 那是一致随机选择的连接到直接地的概率 （创建一个新的边缘 ）;否则，概率 那连接重定向到一个随机选择的邻居的（边缘 )．对于大型 那这导致了无垢程度分布（在原始的KR模型连接中被重定向到祖先的——节点连接到网络时连接;我们的变异产量 ；我们发现，使用原始KR配方与地球夜间卫星照片的相似性较差;此外，我们模型中使用的变体稍微简单一些，因为不需要跟踪祖先)。

接下来考虑节点在空间中的位置，指定 ．对于一个网络节点，基线模型将它们放在一个方形盒内 （定期边界条件）。初始种子节点位于原点， ，以及后续节点的位置取决于它是否连接到节点直接或给邻居 那通过重定向。如果直接连接，放在 从(使用极坐标)，其中的角度 从均匀分布中随机选择，是从分布中随机抽取的吗 在哪里 边界方形中的任何两个点之间的最大可能距离。在重定向的情况下，当节点时连接到 那然后我们简单地在距离从随意的角度 ．增长算法如图所示1（a）．请注意，指数的选择在 （2）相当于 ，这与Kleinberg的“Magic”公式一致，以获得最佳的导航性。

虽然最终选择上述增长规则是为了最好地实现基线模型的目标，但它们也确实具有一定的直觉意义。重定向机制引入了一种“富起来更富”的倾向，这种重定向倾向于节点的随机选择更高的程度。这占无尺度分布的出现。此外，联系和放置规则捕获一些基本的生活方式：一个人他们一出生就加入了现有的社会网络。在这个问题上没有选择，在这种情况下建立的社会连接是随机的(直接连接到节点))．最终离开家，在某个遥远的地方定居。距离的分布新的家，与距离成反比 那是由Kleinberg的“神奇”通航条件激发的[14.那15.］．另一种可能性是通过重定向发生最有意义的社交联系（是指工作场所或学校等)，在这种情况下，在新接触者附近定居是有意义的(距离1是我们距离分布中的最小距离)。

然而，基线SSCN模型的增长规则似乎过于简单，因为它们只解释了最低限度的社会联系:与出生地点的联系由单个链接表示，与处于参照(重定向)情况下的人的联系也是如此。虽然连接的稀疏性可以被证明是合理的，理由是模型是现实生活的缩小版(更少的节点或人，所以每个人更少的接触)，但无法回避的事实是，连接的基线模型网络是一个树，与现实生活中的社交网络形成鲜明对比聚类是大的(你的朋友之间成为朋友的概率高于平均值)。另一个重要的影响是重新搬迁在他们的一生中，人们偶尔会搬到另一个地方，有时不止一次。当人们搬家时，他们会与原籍地的一些熟人保持友谊，并与新邻居建立友谊。因此，搬迁对社会联系网络有着深远的影响。在下一节中，我们将描述修正这些缺点的基线SSCN的新版本。

２.２.修正的SSCN模型

对于目前的模拟，我们使用重定向概率 ，与基线模型相同。这就得到了度指数 这是典型的大型社交网络[34.那35.］．除了我们对模型连接的重大变化外，我们对边界条件和初始种子进行了一些微小的变化，我们首先描述这些。

自由边界条件。在基线模型中，我们使用了一边的边界盒 和周期边界条件。对于目前的工作，我们采用无边界的方法。简单地说，第一个节点被放置在原点，随后的每个节点以与基线模型相同的方式放置，但不考虑边界框。也就是说，允许节点扩展到模拟所允许的范围。我们的模拟表明，即使在这种自由边界条件下，旋转半径的大小也相当精确 那因此，即使模型被缩放，每个单位区域的平均人口密度也保持不变。

最初的种子。从单节点种子开始，如在基线模型中，往往会产生一些比ZIPF分布所预测的少数“巨型巨型”的性能[28.那29.］．在我们的分析中，使用空间城市聚类算法识别城市，该算法在[25.]，并用于我们的基线SSCN模型[24.］．城市聚类算法的主要思想和步骤可以总结如下。首先，将空间域划分为网格(通常是等大小的正方形)，如果单元中的节点数量超过给定的阈值，则确定该单元被“填充”。然后，构建细胞间图，其中节点为填充的细胞，如果对应的细胞在空间上相邻，则两个节点之间存在一条边;也就是说，它们共享一条边界(对角线邻居不计算在内)。最后，将城市定义为cell-to-cell图的连接组件;也就是说，对于城市中的任何一对(人口稠密的)细胞，都存在一条连接它们的路径;另一方面，在属于两个不同城市的两个细胞之间没有这样的路径。由于该算法具有较好的客观性，可以直接从空间人口数据中识别城市。

在 [26.]我们展示了如何通过从由几个节点组成的种子开始来克服Megacities的问题。在这里，我们采用单节点种子，但是，通过节点的数量，重定向概率变化添加之后: 概率迅速收敛到（我们挑选 ）和参数控制收敛的步伐。因此，对于 不同主要影响第一~N_0.节点，但不是网络的大规模结构。另一方面，这个事实 因为前几个节点降低了它们吸引进一步连接的能力，从而缓解了超大城市的问题。值得注意的是，对特殊形式的选择如（3.)不是关键:任何(缓慢)增加的函数，饱和为大原则上可以用来达到减少特大城市发生和规模的效果。的影响城市规模的分布如图所示2(一个)．在图2 (b)我们展示了生产的典型网络的空间布局 ，用颜色突出前三个最大的城市。这种非常相同的配置被用于连通性的研究和下面报道的米尔格拉姆的小世界实验的模拟。

最近的邻居和集群。现在我们来对基线SSCN模型进行更严肃的修订。一个大问题是，基线模型的社会联系网络是一棵树。这意味着你的两个朋友之间成为朋友的概率是零，而在现实生活中，概率实际上高于链接的平均密度，可能是由于人类社会活动和互动的性质[36.］．这种效果最好被概念捕获聚类[37.那38.，对于给定的节点在网络中，被定义为 ,在那里是节点的度数和邻居之间的链路数是多少（ 如果 )．那么，整个网络的聚类系数就是所有节点的平均聚类系数， ．

要解决基线模型中（低）群集的问题，我们现在要求至少连接每个节点它的在地理上最近的邻居，模仿一个人确实倾向于与“隔壁”邻居成为朋友的事实。在生长过程的最后添加新的边缘。新边的添加如图所示1（b）．注意，基线模型对应于的特殊情况 ．

在图3.我们画出网络的聚类系数， 那作为一个函数 ．我们可以看到,非常大，并符合现实生活网络，已经为 ．生长(并随网络规模而减小)，根据经验关系 ．图中的插图显示了单个节点的聚类系数对其度的依赖关系 ．紧急的关系 （ )也是许多现实生活中的典型网络[38.］．

搬迁。基线模型的增长规则，即使添加了连接规则最接近的邻居，仍然无法解释重新定位的非常重要的影响。一个人经常搬到一个新的地方，改变工作或追求教育，婚姻等等。当一个人搬迁时，他们在他们的起源地留住了许多友谊，并在新的位置形成新的友谊。这对社交网络的连接具有深远的影响，正如我们将在下面看到的那样。但是，现在，我们只是描述了在修订后的SSCN模型中融入重新定位的方法。

重新定位一个节点我们首先选择两个节点和随机移动节点在距离 从节点 那而且角度是随机的从 那同时保留所有的连接。在第二阶段，我们检查节点的新环境并添加必要的连接来执行最小值最亲密的邻居规则。请注意，第一阶段仅仅需要改变 那但不是它的联系人。第二阶段确保代理商不仅能保持旧的社会关系，还能在新的地方结交新朋友。搬迁过程如图所示1（c）．

重新定位节点的随机选择和目标节点(或位置)是由人类流动的“重力模型”所驱动的[39.］．它基本上假设任何个人是否和其他的一样有可能搬迁，以及搬迁到任何特定的地方(附近一个地方人口越多，可能性就越大。

在以下部分中，我们研究了迁移分数的效果的系统中的节点。单个重定位会影响重定位节点的程度就像加法一样最亲密的邻居。(但注意,经历了两次这样的更新。)因此，结合效果的衔接最近的邻居和迁移的一部分在度分布上与连通度分布相似 邻居没有迁移。另一方面，搬迁对模式在社交网络的导航和联系上，他们不应该被忽视。

3.结果：连接和Milgram的小世界实验

我们现在转向社交网络所连接的主要问题以及我们可以从Milgram的小世界实验模拟中学到什么。为了具体性，我们研究了图中所示的典型SSCN配置2 (b)并专注于图中最大和第二大城市的个人之间的连通性（人口15,072和5,567）。这两个城市发生了单位长度的距离，和 和“国家”的实际跨度。

3.1。最短的路径

考虑第一次最短路径在网络。最短路径可以非常有效地找到，例如，通过广度优先搜索(BFS)算法。问题是像BFS这样的高效算法所需要的全球的了解整个网络的接触(或整个邻接矩阵)。这种类型的信息显然不是任何人都能得到的，所以仅仅存在最短路径并不能解释米尔格拉姆的小世界实验的结果。然而，最短路径是一个有用的“基准”，人们可以用它来比较各种去中心化算法。

由于社会联系的SSCN网络仅由一个连接组件组成(即使在基线模型中)，任何两个节点之间都存在一条最短的连接路径。我们首先探讨了当一个人将连接性添加到基线模型时最短路径是如何演化的，首先是通过连接 最接近的邻居，然后通过迁移增加的分数 那 那和的节点。

我们的结果为节点之间的最短路径在城市1和节点在城市2总结在图中4.．在基线模型中，两个城市节点之间的最短路径呈钟形分布，平均不到11条。如果连接5个最近的邻居，则最短路径的平均长度约为8.5。这个变化实际上没有人们想象的那么令人印象深刻:基线模型中每个节点的平均程度是 ，因为网络是一个树。添加链接每个节点的最近邻居增加了平均程度 ．我们现在可以将结果与a比较随机网络正在进行类似的变化。由于随机网络中的最短路径是〜 那路径将缩短了一个因素 加入后 邻居。相反，平均路径长度仅减少了令人失望的 ．原因当然是，在我们的例子中，增加的联系远不是随机的，尽管在解释“邻居”朋友的普遍现象时很重要，但它们并没有创造出有效的捷径。对于重新安置来说，情况正好相反:迁移仅仅是节点的部分导致平均路径长度额外缩短到大约7，对于微小的增加是一个巨大的变化 那从到 ．增加迁移率导致平均路径长度的进一步减少，但最戏剧性的变化是在没有迁移之间看到的，并且一小部分重新定位。在这方面，重新定位似乎在瓦特和Strogatz小世界网络中对随机远程连接的角色发挥了类似的作用[37.］．最后，图中的插入显示了每个连续变化的路径长度的分布。随着更多的链路加入，可以将这些分布的缩放追踪到程度分布的均质化。

3.2。贪婪的道路

现在考虑一下米尔格拉姆的小世界实验[13.］．实验参与者只能接触到当地的你知道你的朋友是谁，他们住在哪里，等等，但对他们的朋友几乎一无所知。令人困惑的是，在这种情况下，信息是如何找到它的方向的，更不用说在短短的几个步骤。本地或分散传递消息的算法可能相当复杂，我们将测试几个场景。然而，现在我们坚持最简单的方法贪婪算法:

将信息传递给地理上离目标最近的联系人(假设他比你更近)。

[jonkleinberg14.那15.已经证明，对于他的小世界晶格，没有其他去中心化算法能获得更有利于人口规模的路径比贪心算法要好。换句话说，贪婪路径让我们很好地了解了任何其他分散方法的性能(至少在功能上))．

每个后续节点都是更近目标是重要的：一方面，它保证了融合;另一方面，它意味着当没有比自己更靠近目标的单个联系人时，这条消息可能会被卡住。在这种情况下，源和目标之间没有贪婪的路径。当存在贪婪的道路时，我们说源头和目标是贪婪地连接．在[40］．贪婪连通性的一些更重要的性质如下:(我)通常意义上连接的节点可能不是贪婪连接(但不是反过来)。（ii）贪婪的路径永远不会比最短的路径短。(3)贪婪的连接是不可传递的:如果贪婪地联系在一起和贪婪地联系在一起 那它是不必然的情况是贪婪地联系在一起 ．(iv)贪婪的连接不对称：可能有一个贪婪的路径到但没有贪婪的道路到 ．

我们随机选择了50万对节点 , 和 ，然后寻找贪婪的路径到 那从到 ．结果总结在图中5.．

基线模型的平均贪婪路径长度约为7个环节，非常短;然而,只有它们之间贪婪地联系在一起。添加连接 最近的邻居大大增加了贪婪的连接，到了但平均贪婪路径延长到大约39个链接。这些结果可以理解为:在基线模型中，接触网络是一棵树，有一个独特任何一对节点之间的路径。（该路径也是最短的路径。）由于空间连接以随机角度亮起 那an的概率- 链接到路径到也是一条贪婪的道路吗 ．因此，平均长度的典型最短路径 ，是难以贪婪的概率 ，与观测结果基本一致。连接最近的邻居使得节点对之间有多条路径。贪婪搜索可能在任何特定步骤被放弃的概率大概是(假设最近的邻居是随机分布的，并且忽略底层的基线树)。为 ，则长度为39的典型贪婪路径通过的概率为 ，与观测结果相当吻合。尽管贪婪搜索的成功率大幅提高，但典型的路径长度太大，无法解释米尔格拉姆的小世界实验的观察结果。

甚至迁移一个小部分 的节点进一步提高成功率，至约 那但更重要的是，它削减了典型的贪婪路径长度为2.（请注意，迁移后链接总数增加 到 ，但是4.2%的增长是由 无法解释这些戏剧性的结果。）迁移较大的人群的较大分数只能实现适度的改进。再一次，重定位的作用似乎类似于瓦特和Strogatz小世界网络中的随机远程连接的作用[37.］．然而，典型的贪婪路径长度，约为 那即使对于 对于米尔格拉姆的结果来说，迁移似乎仍然太长了。我们的SSCN模型表明，这种差异很大程度上是由于实验参与者采用了聪明的策略——人们的行为比头脑简单的贪婪算法更聪明——部分原因是由于消耗:在搜索完成前的任何特定步骤放弃任务的非零概率有效地缩短了成功完成的路径的长度。我们接下来讨论这些问题。

3.3。复杂战略和消耗

贪婪路径算法本身无法解释Milgram的小世界实验的结果，我们不得不考虑更复杂的策略。一种可行的策略是，在一定程度上偏爱那些与目标生活得更近的朋友，但也要给那些人脉非常广的朋友一些权重(因为他们可能比我们做出更好的选择)。下面的算法抓住了这个想法的要点。

假设节点目前持有注定（披露的）目标的消息 ．节点分配一个分数每个人熟人（ ）： 在这里和是地理上的距离吗和和和 那和和节点的度是多少和它的分别接触。换句话说，代理商评价他的熟人相对于他自己(他自己的评价是 ），为更近的朋友分配更高的价值比他更有人脉的人。的参数 控制每个属性的相对重要性。凭借手头的分数，策略完全按照贪婪算法进行，但目的是最大化(而不是缩短距离):

将消息传递给具有最大分数的联系人（规定其分数大于1）。

Kleinberg贪婪算法对应于 ．任何其他 该策略仍然保证收敛到目标(如果路径是可用的)，因为距离至本身为零，使其得分是无限的，压倒了所有其他的考虑。(的情况下 是有问题的，因为信息可能无法到达目标，即使是什么时候是…的联系方式 那因此，我们需要 )。寻找一条通往当条款中规定 没有满足。此外，对于 路径可能会重新访问之前接触过的节点，创建一个闭环。当然，在这种情况下，搜索也会被放弃。我们注意到这里所考虑的搜索策略绝不是排他的。在之前的工作中，除了Kleinberg的贪婪算法，还研究了其他几个启发式搜索算法，如[41.在合成和真实的空间网络上。

数字6.总结了这种混合策略的结果，如应用于案例 最近的邻居和 部分搬迁。为了清晰起见，我们只包含从City 2到City 1的搜索结果(反向搜索的微小差异将在下一小节中讨论)。图(a)显示了配对的比例，已成功连接。在插图中显示的整体趋势是快速衰减到零减少。为然而，接近1时，首先有一个增加，从 最多的成功率 ．同时，平均路径长度(图6（b）)减少 在 到 在 ．实际上存在整个范围 混合策略的表现更好(成功率更高)和的纯贪心算法 ．在 例如，成功率与for一样好 ，但平均路径长度被削减了近5个链接。

作为减少之外判断混合策略的成功变得越难：一方面有令人吸引力的效果 ；另一方面，越来越少的对保持连接。解决这个难题的一个方法是选择一个点与米尔格拉姆的小世界实验的成功率大致相当 ．这发生了 ,在那里几乎缩短到几乎链接。

一个重要的结论是，地理上的邻近性是寻找分散路径的最大因素，从较大的值可以看出这在我们的混合策略中是最佳的。这种理解也符合Liben-Nowell等人的研究结果。[20.］．我们的混合策略表明，人们可以比单独的地理更好（案例） )，但没有米尔格拉姆报道的那么好。原因在于，我们的混合策略没有把很多直觉和社交技巧结合起来，而这些都是人们的第二天性。例如，在米尔格拉姆的实验中，除了姓名和地址外，还披露了目标的职业(股票经纪人)。名字包含了目标的性别和种族的线索，地址可能暗示了社会地位。在我们幼稚的方法中没有考虑到这些信息。

更现实的方法可能仍然主要依赖地理位置，至少在信息到达目标城市之前是这样。一旦进入城市，职业、性别、种族、社会地位等额外的线索为寻找更短的路径提供了有效的手段(例如，波士顿的股票经纪人往往互相认识)。事实上，类似米尔格拉姆的实验报告强烈支持这一观点[19.］．我们模拟中目标城市的平均路径明显短于总路径（图6（b）)．在 (我们复制米尔格拉姆的成功率)，则平均路径长度为 ，但只需要4个链接需要到达城市1.在这个阶段，Milgram的结果似乎相当覆盖范围。

到目前为止，我们只考虑了由于战略而被认为是潮流战略的摩擦：当算法未找到下一个有效步骤时，搜索将被删除。然而，在现实生活中，除了有吸引力的选择之外，还有其他原因缺陷：由于忙碌，懒惰，缺乏动机等，参与者可能会从实验中删除。我们指的是这种效果偶然消磨．我们可以将两种类型的磨损转化为单一概率一个人退出实验——这意味着一条长度的路径有完成的机会。来自米尔格拉姆的第二个研究[42.，它可以估计 ．为了说明附带的偶然的效果，在图中6（c）我们画出路径长度的概率分布 那 那就…而言 （实线），以及分布这是由偶然退出概率(虚线)。正如人们所料，总体成功率下降，从到 那但是(有条件的)平均路径长度减少了4.3个链接。这两种类型的损耗是选择较短路径的重要因素。

3．4．不对称

最后考虑贪婪路径的不对称，或者说分散路径在城市1到在城市2不一定与路径相同到 ．我们在图中非常清楚地看到了这种效果5.，其中为城市的平均路径长度 是系统地比City短 ，通过模型建立的所有阶段。从城市1到城市2的成功率也比从城市1到城市2的成功率要低(两者的差异很小，为了简单起见，我们在图中只给出了两者的平均值)。

对这种不对称的简单解释是从城市1到城市2的纯粹贪婪的路径可以通过城市3，但是那些来自城市2到城市的1不能（城市3是远从目标);参见图2 (b)．“直接”通勤，城市的情况是统计上对称的 ，在图片中没有城市3：同样预期的成功路径数量和两方向的平均路径长度。额外的东西 路线往往比直接通勤和账户往往更高的成功率和城市的较长平均路径长度 方向。

我们也观察到小类似的不对称的混合策略，适用于所有值 ．例如，对于伦敦金融城来说，混合策略优于纯贪婪算法的区域就有点窄 方向，有 （代替 为城市 )，但我们没有一个简单的解释来解释这些发现。

4.讨论和结论

总之，我们提出了对[的基线SSCN模型的改进26.]使它适用于动态社交过程的模拟，例如Milgram的小世界实验[13.那42.］．最重要的修订要求将每个节点连接到一些空间上最近的邻居，以考虑“隔壁”的朋友，并重新定位一部分对于节点，要考虑搬迁(由于工作变化、学习、婚姻等)。这两个修正对基线模型的程度分布影响不大，但对社会联系网络的连通性有显著影响:与最近邻居的连接产生了稳健的聚类效应(基线模型中没有)，甚至是很小的一部分重定位引入了远程连接，大大减少了节点对之间的平均路径长度，类似于Watts和Strogatz的小世界网络中的随机远程连接[37.］．

我们对Milgram小世界实验的模拟表明，只有基于节点之间的地理距离的Kleinberg的贪婪算法 - 成功地查找了在节点对之间的分散路径，但路径太长而无法解释MILGRAM的结果。我们已经表明，更复杂的策略，例如偶尔将消息传递给特别良好连接的熟人，可以导致路径长度的显着降低。我们还确认了地理位置是寻找短路的最重要考虑因素[19.那20.]至少在初始阶段，直到消息到达目标城市。在城市内，目标的剩余路径可以大大缩短，使用额外的明确信息（例如，占用）和关于目标的隐性信息（种族，社会地位）。我们还讨论了磨损的效果（参与者因各种原因退出实验的事实），并显示了如何帮助选择较短的路径。请注意，最近已经基于映射到超周测量空间的可导航空间网络的替代模型[43.或一些迭代优化技术[44.］．

Milgram的实验模拟对SSCN模型构成了特别严格的测试，在该模型中，找到分散的路径依赖于节点的位置和它们的连接网络。该模型的成功使其成为对社交网络上其他动态过程进行模拟的有希望的基板，其中这些考虑是重要的（流行病，意见模型等）。

附录

空间社会复杂网络(SSCN)模型的算法描述

在算法1我们提供了使用(修订的)SSCN模型生成空间社会网络的伪代码。如正文中所讨论的，重定向参数的典型选择是 和 ．

的利益冲突

作者声明他们没有利益冲突。

致谢

这项工作部分是由西蒙斯基金会资助的。318812和陆军研究办公室批准号。w911nf - 16 - 1 - 0081。

参考文献

1. R. Pastor-Satorras和A. Vespignani， "流行病在无尺度网络中传播"物理评论信，第86卷，第86期14，页3200-3203,2001。视图:出版商网站|谷歌学者
2. R. Cohen，S. Havlin和D. Ben-Avraham，“计算机网络和人口的高效免疫策略”，物理评论信第91卷第1期24、文章编号247901,2003年。视图:谷歌学者
3. V. Belik, T. Geisel，和D. Brockmann，“自然的人类流动模式和传染病的空间传播”，物理评论X， vol. 1, no. 11、文章编号011001,pp. 1 - 5, 2011。视图:出版商网站|谷歌学者
4. J. Kim, E. Elliott，和D. M. Wang，“1988-2000年美国总统选举县级结果的空间分析”，选举的研究，卷。22，没有。4，pp。741-761,2003。视图:出版商网站|谷歌学者
5. S. Kwon, M. Cha, K. Jung, W. Chen, Y. Wang，“网络社交媒体中谣言传播的突出特征”，刊于第13届IEEE数据挖掘国际会议论文集，ICDM 2013，第1103-1108页，美国，2013年12月。视图:出版商网站|谷歌学者
6. Y. Hu, S. Havlin，和H. A. Makse，“病毒影响通过多重相关社交网络传播的条件”，物理评论X，第4卷，第4期。2、文章编号021031,2014。视图:出版商网站|谷歌学者
7. 《网络结构、竞争和记忆时间对社会传播现象的影响》，《中国社会科学》，2013年第4期。物理评论X，第6卷，第2期2、文章编号021019,2016。视图:出版商网站|谷歌学者
8. L.翁，a . Flammini, a . Vespignani, F. menzer，《在有限关注的世界里模因的竞争》科学报告，第2卷，第335篇，8页，2012年。视图:出版商网站|谷歌学者
9. D. Brockmann, L. Hufnagel和T. Geisel，《人类旅行的尺度法则》，自然，第439卷，第2期。7075，第462-465页，2006。视图:出版商网站|谷歌学者
10. S. H. Lee，R.Ffrancon，D. M. Abrams，B. J. Kim和M. A. Porter，“Matchmaker，Matchmaker，让我一场比赛：过去通过婚姻迁移人口迁移，”物理评论X，第4卷，第4期。4、Article ID 041009, 2014。视图:出版商网站|谷歌学者
11. L. M. A.贝当古，《城市规模扩张的起源》，美国科学促进会:科学，卷。340，没有。6139，第1438-1441,2013。视图:出版商网站|谷歌学者|MathSciNet
12. M.Schläpfer，L.M.Bettencourt，S. Grauwin等，“与城市规模的人类互动的扩展”皇家社会界面杂志，卷。11，不。98，pp。20130789-20130789,2014。视图:出版商网站|谷歌学者
13. S.米尔格拉姆，《小世界问题》今日心理学，第1卷，第60 - 67,1967年。视图:谷歌学者
14. J. M. Kleinberg，“在一个小世界导航”，自然，卷。406，没有。6798，p。845,2000。视图:出版商网站|谷歌学者
15. J. Kleinberg，《小世界现象:算法视角》第32届美国计算机学会计算理论年会论文集，STOC 2000，页163-170，美国，2000年5月。视图:出版商网站|谷歌学者
16. 罗伯逊和本-亚伯拉罕，《小世界网络中的克莱恩伯格导航》，物理评论E：统计，非线性和软质物理，卷。74，没有。1，物品ID 017101,2006。视图:出版商网站|谷歌学者
17. J. M. Campuzano，J.P.Bagrow和D. Ben-Avraham，“克莱辛伯格在各向异性格子上导航”，物理学中的研究信，卷。2008，第1-4,2008。视图:出版商网站|谷歌学者
18. D. Rybski, A. García Cantú Ros和J. P. Kropp，《距离加权城市增长》，物理评论E：统计，非线性和软质物理，卷。87，没有。4，第20113年，2013年。视图:出版商网站|谷歌学者
19. P. S. Dodds, R. Muhamad，和D. J. Watts，《全球社交网络搜索的实验研究》，科学第301卷第1期2003年。视图:出版商网站|谷歌学者
20. D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan，和A. Tomkins，《社交网络中的地理路由》，美国国家科学院学报第102卷第1期33, pp. 1623 - 1628, 2005。视图:出版商网站|谷歌学者
21. S. Scellato, A. Noulas, R. lambitte，和C. Mascolo，“基于位置的在线社交网络的社会空间属性”，刊于第五届AAAI国际博客与社交媒体会议论文集(ICWSM, 2011)，p。5，巴塞罗那，西班牙，2011年。视图:谷歌学者
22. P. Expert, T. S. Evans, V. D. Blondel，和R. lambitte，“揭示空间网络中的空间独立社区”，美国国家科学院学报，卷。108，没有。19，pp。7663-7668，2011年。视图:出版商网站|谷歌学者
23. J. P. onneela, S. Arbesman, M. C. González, A. L. Barabási, N. A. Christakis，《社交网络群体的地理限制》，《公共科学图书馆•综合》，第6卷，第2期4、Article ID e16939, 2011。视图:出版商网站|谷歌学者
24. M. Barthélemy，“空间网络”，物理报告号，第499卷。1-3, pp. 1-101, 2011。视图:出版商网站|谷歌学者
25. m·巴特尔米城市的结构与动态，剑桥大学出版社，剑桥，2016年。视图:出版商网站
26. G. F. Frasco, J. Sun, H. D. Rozenfeld，和D. Ben-Avraham，“空间分布的社会复杂网络”，物理评论X，第4卷，第4期。1、文章编号011008,2014。视图:出版商网站|谷歌学者
27. H. D. Rozenfeld, D. Rybski, J. S. Andrade Jr, M. Batty, H. E. Stanley, H. A. Makse，《人口增长定律》，美国国家科学院学报第105卷第1期48，第18702-18707页，2008。视图:出版商网站|谷歌学者
28. G. Zipf，人类行为与最小努力原则， Addison-Wesley，剑桥，马萨诸塞州，美国，1949。
29. M. Cristelli, M. Batty，和L. Pietronero，“在齐普夫，不仅有幂次定律，”科学报告，第2卷，第1号812年,2012年。视图:出版商网站|谷歌学者
30. T. Fluschnik, S. Kriewald, A. G. C. Ros等，“城市集群的规模分布、尺度属性和空间组织:全球和区域的渗透视角，”ISPRS国际地理信息杂志，第5卷，第5期。7、文章ID 638868205, 2016。视图:出版商网站|谷歌学者
31. P.L.Krapivsky和S. Redner，“种植随机网络的组织”，物理评论E：统计，非线性和软质物理，第63卷，第2期文章编号066123,2001。视图:谷歌学者
32. P. L. Krapivsky和S. Redner，《成长网络中的有限性和波动》，物理学报A:数学与一般，卷。35，不。45，pp。9517-9534，2002。视图:出版商网站|谷歌学者|MathSciNet
33. J. Kim, P. L. Krapivsky, B. kang, and S. Redner，“蛋白质相互作用网络中的无限阶渗透和巨大波动”，物理评论E：统计，非线性和软质物理第66期5、Article ID 055101, p. 055101/4, 2002。视图:出版商网站|谷歌学者
34. R. Albert和A.L.Barabási，“复杂网络的统计机制”，现代物理学评论，卷。74，没有。1，pp。47-97,2002。视图:出版商网站|谷歌学者|MathSciNet
35. M. E.纽曼，《复杂网络的结构和功能》，暹罗审查第45卷第5期2，页167-256,2003。视图:出版商网站|谷歌学者|MathSciNet
36. L. K. Gallos, D. Rybski, F. Liljeros, S. Havlin, and H. A. Makse，“人们如何在不断发展的在线从属网络中互动，”物理评论X，第2卷，第2期3、文章ID 031014, 2012。视图:出版商网站|谷歌学者
37. d·j·沃茨和s·h·斯特罗加茨，《小世界网络的集体动力》，自然，卷。393，没有。6684，PP。440-442，1998。视图:出版商网站|谷歌学者
38. S. Boccaletti、V. Latora、Y. Moreno、M. Chavez和d - u。《复杂网络:结构与动力学》物理报告，卷。424，没有。4-5，pp.175-308，2006。视图:出版商网站|谷歌学者
39. N. Bharti, Y. Xia, O. N. Bjornstad，和B. T. Grenfell，《麻疹的边缘:沿海的异质性和感染动态》，《公共科学图书馆•综合》，第3卷，第2期。文章编号e1941, 2008。视图:出版商网站|谷歌学者
40. J. Sun和D. Ben-Avraham，《地理嵌入图的贪婪连通性》，物理评论E：统计，非线性和软质物理，第82卷，第2期1、文章编号016109,2010。视图:出版商网站|谷歌学者
41. H. P. Thadakamalla, R. Albert和S. R. T. Kumara，《空间无尺度网络的搜索》，新物理学杂志第9卷第1号条款190年,2007年。视图:出版商网站|谷歌学者
42. J. Travers和S. Milgram，“对小世界问题的实验研究”人与人之间，第32卷，第2期4，页425-443,1969。视图:出版商网站|谷歌学者
43. D. Krioukov，F.Papadopoulos，M. Kitsak，A. Vahdat和M.Boguñá，“复杂网络的双曲线几何”，“物理评论E：统计，非线性和软质物理，第82卷，第2期3，图1036106，2010。视图:出版商网站|谷歌学者
44. Y. A. Malkov和A. Ponomarenko，“成长中的同性恋网络是自然可航行的小世界，”《公共科学图书馆•综合》，卷。11，不。6，物品ID E0158162,2016。视图:出版商网站|谷歌学者

版权

版权所有©2018 Shandeepa Wickramasinghe等。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。