• 三角中心性;
• 随机增长模型中财富不平等的统计动力学;
• 气候物理学：对反复发生的历史事件的科学分析;
• 用于种群和网络中随机多智能体动力学的 Gillespie 算法;
• SLUGGER：海量图的无损分层汇总;
• 随机多人博弈;
• 观察游走中的顺序模体;

三角中心性

原文标题： Triangle Centrality

地址： http://arxiv.org/abs/2105.00110

作者： Paul Burkhardt

摘要： 引入三角形中心性以根据围绕每个顶点的三角形的集中度在图中找到重要的顶点。三角形中心性的一个重要顶点位于许多三角形的中心，因此它可能在许多三角形中或根本没有。我们给出了在 O(msqrtm) 时间和 O(m+n) 空间中计算三角形中心性的最佳算法。使用快速矩阵乘法需要 n^omega+o(1) 时间，其中 omega 是矩阵乘积指数。在并发读独占写入 (CREW) 并行随机存取存储器 (PRAM) 机器上，我们给出了一个接近工作最优的算法，该算法使用 O(msqrtm) CREW 花费 O(log n) 时间PRAM 处理器。在 MapReduce 中，我们展示了使用 O(msqrtm) 通信位需要四轮，因此是最佳的。我们还给出了一个确定性算法来在 O(msqrtm) 时间和 O(m+n) 空间中找到每个顶点的三角形邻域和三角形计数。我们的实证结果表明，与其他五个众所周知的中心性度量相比，三角形中心性在 30% 的时间内唯一标识了中心顶点，同时在稀疏图上的计算速度比其他所有度量都快。

随机增长模型中财富不平等的统计动力学

原文标题： Statistical Dynamics of Wealth Inequality in Stochastic Models of Growth

地址： http://arxiv.org/abs/2112.05217

作者： Jordan Kemp, Luis M. A. Bettencourt

摘要： 理解增长和不平等的统计动态是生态和社会面临的一项根本挑战。最近对当代社会财富和收入动态的分析表明，经济不平等是非常动态的，随着时间的推移，个人经历了截然不同的增长率。然而，尽管有大量证据表明波动的重要性，但我们仍然缺乏通用的统计理论来理解人口异质增长的动态影响。在这里，我们推导出异质人群中相关增长率的统计动态。我们表明，个体层面的增长率波动之间的相关性会影响总体人口增长，而只会在短时间内推动不平等。我们还发现，与收益波动相比，增长率波动是长期不平等的更大驱动力。我们的研究结果表明，增长率统计波动的动态影响对于理解不平等随时间推移的出现至关重要，并促使人们更加关注随机环境中增长率的特性和内生起源。

气候物理学：对反复发生的历史事件的科学分析

原文标题： Cliophysics: A scientific analysis of recurrent historical events

地址： http://arxiv.org/abs/2112.05225

作者： Yuji Aruka, Belal Baaquie, Xiasong Chen, Zengru Di, Beomjun Kim, Peter Richmond, Bertrand M. Roehner, Qing-hai Wang, Yang Yang

摘要： 以希腊历史女神克里奥命名，气候物理学是经济物理学的女儿（在某种意义上是一种延伸）。像经济物理学一样，它依赖于实验物理学的方法论。其目的是对历史事件进行科学分析。此类事件可能具有社会、政治或经济性质。在最后一种情况下，气候物理学将与经济物理学相吻合。气候物理学和经济物理学之间的主要区别在于，对历史事件的描述可能是定性的，也可能是定量的。为了处理定性帐户，气候物理学开发了一种基于模式识别的方法。检测模式的主要挑战是打破“噪音屏障”。模式的存在正是使气候物理学成为可能并确保其成功的原因。简而言之，一旦检测到模式，就可以进行预测。由于做出成功预测的能力是任何科学的标志，因此很容易确定论文标题中提出的主张是否确实得到了满足。将给出许多类似事件集群的例子，它们应该使读者相信历史事件几乎可以像物理学一样被随意简化。不应忘记，物理效应也受环境影响。例如，如果在赤道上尝试，傅科摆的实验就会失败。在论文的最后一部分，我们描述了过去几十年进行的气候物理学调查；它们使我们相信气候物理学可以成为决策者的宝贵工具。

用于种群和网络中随机多智能体动力学的 Gillespie 算法

原文标题： Gillespie algorithms for stochastic multiagent dynamics in populations and network

地址： http://arxiv.org/abs/2112.05293

作者： Naoki Masuda, Christian L. Vestergaard

摘要： 许多多主体动态，包括发生在网络上的各种集体动态，可以被建模为一个随机过程，其中系统中的主体随着时间的推移相互交互改变它们的状态。 Gillespie 算法是一种流行的算法，当每个状态变化由离散事件驱动时，精确模拟这种随机多智能体动态，动态定义为连续时间，事件发生的随机定律由独立的泊松过程控制。在本卷的第一部分，我们提供了一个关于 Gillespie 算法的教程，重点是模拟人口和网络中发生的社会多主体动态。我们不假设具有数学（或计算机科学或物理学）的高级知识。我们阐明了为什么在许多情况下应该使用连续时间模型和 Gillespie 算法，而不是更容易理解的离散时间模型。在本卷的其余部分，我们回顾了 Gillespie 算法的最新扩展，旨在为模型添加更多真实性（即非泊松情况）或加速模拟。

SLUGGER：海量图的无损分层汇总

原文标题： SLUGGER: Lossless Hierarchical Summarization of Massive Graphs

地址： http://arxiv.org/abs/2112.05374

作者： Kyuhan Lee, Jihoon Ko, Kijung Shin

摘要： 给定一个庞大的图，我们如何利用它的层次结构来简洁而准确地总结图？通过利用这种结构，我们能否获得比最先进的图摘要方法更好的压缩率？ Web 的爆炸式增长加速了大型图的出现，例如在线社会网络和超链接网络。因此，图压缩对于处理如此大的图变得越来越重要，而无需通过网络或磁盘进行昂贵的 I/O。在众多方法中，本质上将相似节点组合成一个超级节点并简洁地描述它们的连接性的图摘要具有几个优点。然而，我们注意到它未能利用现实世界图的普遍层次结构，因为其底层表示模型强制超节点不相交。在这项工作中，我们提出了层次图摘要模型，这是一种富有表现力的图表示模型，包括 Navlakha 等人提出的前一个模型。作为特例。新模型使用分层超节点之间的正负边表示未加权图，每个超节点可以包含其他。然后，我们提出了 Slugger，这是一种可扩展的启发式方法，用于在我们的新模型下简洁准确地表示给定的图。 Slugger 贪婪地将节点合并为超级节点，同时维护和利用它们的层次结构，然后对其进行修剪。 Slugger 通过采样、近似和记忆显著加速了这个过程。我们在 16 个真实世界的图上的实验表明，Slugger 是 (a) 有效的：比最先进的无损总结方法产生高达 29.6% 的简洁总结，(b) 快速：总结具有 8 亿条边的图几个小时，以及 © 可扩展：随输入图中的边数线性尺度。

随机多人博弈

原文标题： Random multi-player games

地址： http://arxiv.org/abs/2112.05601

作者： Natalia L. Kontorovsky, Juan Pablo Pinasco, Federico Vazquez

摘要： 许多不同学科都对具有成对局部相互作用的演化博弈研究感兴趣。还考虑了与多个对手的本地互动，尽管总是针对固定数量的玩家。然而，在许多情况下，每一轮中不同数量的玩家之间可能会发生互动，这种情况不能简化为成对互动。在这项工作中，我们对演化稳定策略 (ESS) 的定义进行形式化和概括，以便能够包括一个场景，其中两个玩家以概率 p 玩博弈，三个玩家以互补概率 1-p 玩博弈.我们展示了纯策略和混合策略中均衡的存在，这取决于概率 p，在决斗-真实博弈的一个具体例子中。我们找到了一系列 p 值，在这些范围内，博弈具有混合均衡，并且每个策略中玩家的比例取决于 p 的特定值。我们证明这些混合平衡点中的每一个都是 ESS。研究这种具有高阶相互作用的动态的更现实的方法是研究它在复杂网络中的演变方式。我们在具有固定节点数的网络上引入并研究了基于主体的模型，该模型随着复制器方程的预测而发展。通过研究该模型在随机网络上的动力学，我们发现纯平衡和混合平衡之间的相变取决于概率 p 以及网络的平均度。

观察游走中的顺序模体

原文标题： Sequential Motifs in Observed Walks

地址： http://arxiv.org/abs/2112.05642

作者： Timothy LaRock, Ingo Scholtes, Tina Eliassi-Rad

摘要： 复杂网络的结构可以通过计算和分析网络模体来表征。母题是在网络中重复出现的小子图，例如三角形或链。最近的工作将模体推广到时间和动态网络数据。然而，现有技术不能推广到表示通过网络节点移动的实体的顺序或轨迹数据，例如通过交通网络移动的乘客。这些数据中的观察单位根本不同，因为我们分析轨迹的完整观察结果（例如，从机场 A 到机场 C 通过机场 B），而不是随着时间的推移对边或图快照的独立观察。在这项工作中，我们在轨迹数据中定义了顺序模体，它们是与观察到的序列中的模式相对应的小、有向和边加权子图。我们将连续模体的计数和分析与高阶网络 (HON) 模型联系起来。我们表明，通过将 HON 的边（特别是 kth 阶 DeBruijn 图）映射到顺序模体，我们可以计算和评估它们在观察数据中的重要性。我们使用两个数据集测试我们的方法：(1) 乘客在机场网络中导航和 (2) 人们在 Wikipedia 文章网络中导航。我们发现最普遍和最重要的序列模体对应于真实系统中的直观遍历模式，并凭经验表明观察到的高阶 DeBruijn 图中边权重的异质性对我们期望看到的序列模体的分布有影响在我们的空模型中。

声明：Arxiv文章摘要版权归论文原作者所有，机器翻译后由本人进行校正整理，未经同意请勿随意转载。本系列在微信公众号“网络科学研究速递”（微信号netsci）和个人博客 https://netsci.complexly.cn （提供RSS订阅）进行同步更新。个性化论文阅读与推荐请访问 https://arxiv.complexly.cn 平台。