• 时间网络上影响最大化的有效子模性;
• 度异构网络上双井系统的平均场理论;
• 通过具有度约束的短路径最小化直径;
• 使用符号网络分析和可视化美国国会的两极分化和平衡;
• 结构保持图表示学习;
• 使用随机顺序吸附过程对密集 CSMA 网络进行建模;
• 影响最大化的可扩展对抗性攻击算法;
• 有向复杂网络上的意见动态;
• 强化学习的内在波动促进合作;
• 人才流失的数字痕迹：俄罗斯入侵乌克兰期间的开发人员;
• 有向网络的距离主干;

时间网络上影响最大化的有效子模性

原文标题： Effective submodularity of influence maximization on temporal networks

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

作者： Sirag Erkol, Dario Mazzilli, Filippo Radicchi

摘要： 我们研究时间网络上的影响最大化。这是一个特殊设置，其中影响函数不是次模的，并且通过贪心优化获得的解决方案没有最优性保证。我们对真实网络和合成网络进行了详尽的分析。我们表明，随机抽样的种子集的影响函数经常违反子模块化的必要条件。然而，当根据贪心优化策略选择种子集时，影响函数有效地表现为子模函数。具体来说，在实际网络中从未观察到违反子模块化必要条件的情况，在合成网络中也很少观察到。与通过蛮力搜索获得的精确解的直接比较表明，贪心策略提供的近似解完全在严格的子模函数保证的最优性差距内。因此，贪心优化似乎是最大化对时间网络的影响的有效策略。

度异构网络上双井系统的平均场理论

原文标题： Mean-field theory for double-well systems on degree-heterogeneous networks

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

作者： Prosenjit Kundu, Neil G. MacLaren, Hiroshi Kori, Naoki Masuda

摘要： 现实世界中的许多复杂动力系统，包括生态系统、气候系统、金融系统和电网系统，经常会出现关键的转变或临界点，在这些转变中，系统的动力学会突然转变为质的不同状态。在数学模型中，临界点发生在控制参数逐渐变化并超过某个阈值时。这种系统中的小费元素可以作为一个网络相互交互，并且由于源自网络的高维性，理解交互小费元素的行为是一个挑战。在这里，我们为耦合在网络上的原型双井系统开发了一种基于度数的平均场理论，目的是通过低维描述来理解耦合倾翻动力学。该方法以合理的精度逼近临界点的开始和平衡的位置。基于发达的理论和数值模拟，我们还为双井系统网络中的多阶段临界点转变提供了证据。

通过具有度约束的短路径最小化直径

原文标题： Diameter Minimization by Shortcutting with Degree Constraints

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

作者： Florian Adriaens, Aristides Gionis

摘要： 我们考虑向无向图添加固定数量的新边以最小化增广图的直径的问题，并且在为每个顶点添加的边数以整数为界的约束下。这个问题是由网络设计应用程序引起的，我们希望在不过度增加任何单个顶点的度数的情况下最小化网络中最坏情况的通信，以避免额外的过载。我们为这项任务提出了三种算法，每种算法都有自己的优点。匹配增强的特殊情况，当每个顶点最多可以入射到一个新边时，这是特别有趣的，我们展示了一个不可近似的结果，并在这些边添加到路径时提供了最小可实现直径的界限.最后，我们在几个不同类型的真实网络上对我们的算法进行了实证评估和比较。

使用符号网络分析和可视化美国国会的两极分化和平衡

原文标题： Analyzing and Visualizing American Congress Polarization and Balance with Signed Networks

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

作者： Arthur Capozzi, Alfonso Semeraro, Giancarlo Ruffo

摘要： 有符号网络和平衡理论为显示极化动态、正/负关系和政治党派关系的现实世界场景提供了一个自然环境。例如，它们已被证明有效地研究了二战以来美国国会两院投票日益分化的情况。为了进一步深入理解这个特定的案例研究，我们建议应用一个框架来分析和可视化符号图的配置，该配置基于对相应拉普拉斯矩阵的谱特性的利用。基于挫折指数，整体方法与其他方法相当，但它至少有两个主要优点：首先，它需要低得多的计算成本；其次，它允许对任意小的子图（甚至是单个节点）对网络整体平衡（或不平衡）的贡献进行定量和直观的评估。拟议的管道允许探索美国国会从 1945 年到 2020 年在不同分辨率尺度下显示的极化动态。事实上，我们能够发现并指出一些（群体）议员对整体平衡的影响，以及观察和探索两院多年来两极分化的演变。

结构保持图表示学习

原文标题： Structure-Preserving Graph Representation Learning

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

作者： Ruiyi Fang, Liangjian Wen, Zhao Kang, Jianzhuang Liu

摘要： 尽管图表示学习（GRL）取得了重大进展，但以适当的方式提取和嵌入丰富的拓扑结构和特征信息仍然是一个挑战。现有的方法大多侧重于局部结构，未能完全融入全局拓扑结构。为此，我们提出了一种新颖的结构保持图表示学习（SPGRL）方法，以充分刻画图的结构信息。具体来说，为了减少原始图的不确定性和错误信息，我们通过 k-Nearest Neighbor 方法构建了一个特征图作为互补视图。特征图可用于在节点级别进行对比以刻画局部关系。此外，我们通过最大化整个图和特征嵌入的互信息（MI）来保留全局拓扑结构信息，理论上可以简化为交换特征和原始图的特征嵌入来重建自身。大量实验表明，我们的方法在半监督节点分类任务上具有相当优越的性能，并且在噪声扰动下对图结构或节点特征具有出色的鲁棒性。

使用随机顺序吸附过程对密集 CSMA 网络进行建模

原文标题： Modeling of Dense CSMA Networks using Random Sequential Adsorption Process

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

作者： Priyabrata Parida, Harpreet S. Dhillon

摘要： 我们对密集无线局域网进行建模，其中接入点 (AP) 采用载波侦听多路访问 (CSMA) 型媒体访问控制协议。在我们的模型中，活性 AP 集合的空间位置使用随机顺序吸附 (RSA) 过程建模，与II 型 (MHPP-II) 通常用于对 CSMA 网络进行建模。利用统计物理学文献中的 RSA 过程理论，我们为网络中典型 AP 的介质访问概率提供了一个近似但准确的分析结果。此外，我们提出了一种数值方法来确定对相关函数 (mathttPCF)，这对于准确估计干扰统计数据很有用。使用 mathttPCF 结果，我们推导出网络中典型链路的信干噪比覆盖概率。我们通过广泛的蒙特卡罗模拟验证了理论结果的准确性。

影响最大化的可扩展对抗性攻击算法

原文标题： Scalable Adversarial Attack Algorithms on Influence Maximization

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

作者： Lichao Sun, Xiaobin Rui, Wei Chen

摘要： 在本文中，我们研究了社会网络中动态影响传播模型下对影响最大化的对抗性攻击。特别是，给定一个已知的种子集 S，问题是通过删除有限数量的节点和边来最小化从 S 传播的影响。这个问题反映了许多应用场景，例如通过隔离和接种疫苗来阻止病毒（例如COVID-19）在社会网络中传播，通过冻结虚假账户来阻止谣言传播，或者通过激励一些用户忽略来自竞争对手的信息来攻击竞争对手的影响力。在本文中，在线性阈值模型下，我们采用反向影响采样方法并提供有效的反向可达路径采样的有效算法来解决该问题。

有向复杂网络上的意见动态

原文标题： Opinion dynamics on directed complex networks

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

作者： Nicolas Fraiman, Tzu-Chi Lin, Mariana Olvera-Cravioto

摘要： 我们提出并分析了一个数学模型，用于对有向复杂网络的意见演变。我们的模型通过允许顶点具有可能影响意见动态的属性来概括流行的 DeGroot 和 Friedkin-Johnsen 模型。我们首先建立在任何固定图上存在平稳意见分布的充分条件，然后通过考虑具有局部弱限制的有向随机图序列来提供其行为的越来越详细的表征。我们最明确的结果是针对其局部弱极限是标记的 Galton-Watson 树的图序列获得的，在这种情况下，我们的模型可以用来解释各种现象，例如，可以达成共识的条件，意见的机制可能会变得两极分化，以及破坏性顽固主体人对意见形成的影响。

强化学习的内在波动促进合作

原文标题： Intrinsic fluctuations of reinforcement learning promote cooperation

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

作者： Wolfram Barfuss, Janusz Meylahn

摘要： 在这项工作中，我们询问并回答使经典强化学习合作的原因。在社会困境中进行合作对动物、人类和机器来说都是至关重要的。虽然演化理论揭示了一系列促进合作的机制，但智能体学习合作的条件存在争议。在这里，我们展示了多智能体学习环境中的哪些单个元素以及如何导致合作。具体来说，我们考虑在具有单周期记忆的迭代囚徒困境的经典环境中广泛使用的时差强化学习算法与 epsilon-greedy 探索。两个学习主体中的每一个都学习一种策略，该策略将以下动作选择作为两个主体在上一轮的动作选择的条件。我们发现，除了对未来奖励的高度关注、低探索率和小学习率之外，主要是强化学习过程的内在随机波动使最终合作率翻倍，达到 80%。因此，固有噪声并不是迭代学习过程的必然弊端。它是学习合作的重要资产。然而，我们也指出了合作行为的高可能性与在合理时间内实现这一目标之间的权衡。我们的研究结果与有目的地设计合作算法和调节不希望的合谋效应有关。

人才流失的数字痕迹：俄罗斯入侵乌克兰期间的开发人员

原文标题： Digital Traces of Brain Drain: Developers during the Russian Invasion of Ukraine

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

作者： Johannes Wachs

摘要： 俄罗斯入侵乌克兰引发了对人才外流现象的新兴趣：人力资本外流。然而，量化人才流失，尤其是在危机情况下实时量化，仍然很困难。这阻碍了我们理解其驱动因素和机制并预测其后果的能力。为了弥补这一差距，我利用并扩展了在入侵前一年的 2021 年 2 月收集的高度活跃的软件开发人员位置的大规模数据集。回顾那些在 2021 年位于俄罗斯的开发人员，我确认到 2022 年 6 月下旬，大量开发人员从俄罗斯撤离。8.6% 的俄罗斯开发人员列出了一个新的国家，而该地区可比国家的开发人员为 2.4%，但没有直接卷入冲突。 11.3% 的俄罗斯开发商隐藏了他们的位置（对比组为 1.9%）。我们的数据还使我们能够观察谁离开和谁留下的异质性，并理解他们的去向。离开俄罗斯的开发者在协作网络中的积极性和核心地位明显高于留下来的开发者。这表明最重要的开发商已经离开了俄罗斯。

有向网络的距离主干

原文标题： The distance backbone of directed networks

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

作者： Felipe Xavier Costa, Rion Brattig Correia, Luis M. Rocha

摘要： 在加权图中，两个节点之间的最短路径通常通过间接路径到达，在所有可能的连接中，导致结构冗余，这在复杂网络的动态和演化中起关键作用。我们之前开发了一种无参数、代数原理的方法来揭示这种冗余并揭示加权图的距离主干，这已被证明在传输动力学、重要路径的推断和量化网络的鲁棒性方面很重要。然而，该方法是为无向图开发的。在这里，我们将这种方法扩展到加权有向图，并研究在社会、生物医学和技术系统等九个网络中发现的冗余和鲁棒性。我们发现，与无向图类似，有向图通常也包含大量冗余，这是通过其（有向）距离骨干的大小来衡量的。我们的方法为复杂网络的原则稀疏化及其鲁棒性的测量增加了一个额外的工具。

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