核心速递

用于符号网络的聚类和半监督聚类的MBO方案;
多个传播路径增强了在复杂网络中定位扩散源的能力;
基于移动电话使用模式和社会网络拓扑的人口属性推断;
谣言源头与正则树上最优估计的距离;
时尚和艺术周期受到精英竞争的反主导信号的驱动：音乐风格的定量证据;
浪漫伴侣算法匹配中的无政府状态价格;
给定相关组件中断的级联停电风险;

用于符号网络的聚类和

半监督聚类的MBO方案

原文标题：

An MBO scheme for clustering and semi-supervised clustering of signed networks

地址：

http://arxiv.org/abs/1901.03091

作者：

Mihai Cucuringu, Andrea Pizzoferrato, Yves van Gennip

摘要： 我们为有符号聚类问题引入了一种有原则的方法，其目标是对边权重为正值和负值的图进行分区，使得同一聚类中的边大部分为正，而跨越聚类的边大部分为负。我们的方法依赖于基于图的漫反射界面模型公式，该公式利用Ginzburg-Landau功能，基于经典数值Merriman-Bence-Osher（MBO）方案的改编，以最小化这种基于图的功能。所提出的目标函数旨在最小化簇间正加权边的总权重，同时最大化簇间负加权边的总权重。

我们的方法可扩展到大型稀疏网络，并且可以轻松调整以包含标记数据信息，这在半监督学习的背景下通常就是这种情况。我们在许多合成随机块模型和现实世界数据集（包括金融相关矩阵）上测试了我们的方法，并获得了有希望的结果，这些结果与最近文献中的许多最先进的方法相比是有利的。

多个传播路径增强了在复

杂网络中定位扩散源的能力

原文标题：

Multiple propagation paths enhance locating the source of diffusion in complex networks

地址：

http://arxiv.org/abs/1901.02931

作者：

Łukasz Gajewski, Jan Chołoniewski, Janusz Hołyst

摘要： 我们研究了在没有完全了解节点状态的情况下在复杂网络中定位扩散源的问题。一些当前已知的方法假设信息通过单个最短路径传播，这通过假设是最快的方式。我们表明，这种方法导致高估合成和真实网络的传播时间，其中存在多个最短路径以及顶点之间的较长路径。我们提出了一种基于最大似然原理的源估计新方法，该方法考虑了存在多个最短路径。它在合成和真实网络中的准确度高达1.6倍。

基于移动电话使用模式和

社会网络拓扑的人口属性推断

原文标题：

Inference of Demographic Attributes based on Mobile Phone Usage Patterns and Social Network Topology

地址：

http://arxiv.org/abs/1901.02932

作者：

Carlos Sarraute, Jorge Brea, Javier Burroni, Pablo Blanc

摘要： 移动电话的使用提供了丰富的信息，可用于更好地了解人口的人口结构。在本文中，我们关注墨西哥手机用户的人口。我们首先根据性别和年龄组提出手机使用情况的观察性研究。我们能够检测到不同人群中电话使用的显著差异。然后，我们研究不同机器学习（ML）方法的性能，通过利用个体呼叫模式以及通信图的结构来预测未标记用户的人口统计特征（即年龄和性别）。

我们展示了利用图结构的扩散模型的具体实现如何比其他基于节点的标准ML方法具有明显更好的性能。我们提供了该方法的详细信息，并分析了我们的结果对模型参数变化的稳健性。此外，通过仔细检查训练节点（种子节点）与网络中其余节点的拓扑关系，我们发现拓扑指标直接影响算法的性能。

谣言源头与正则树

上最优估计的距离

原文标题：

On the Distance Between the Rumor Source and Its Optimal Estimate on a Regular Tree

地址：

http://arxiv.org/abs/1901.03039

作者：

Tetsunao Matsuta, Tomohiko Uyematsu

摘要： 本文讨论了谣言来源识别问题，其目标是在谣言中找到一组给定节点中网络中谣言的起源节点。在本文中，我们关注由常规树表示的网络，该树没有任何循环，并且所有节点具有连接到节点的相同数量的边。对于该网络，我们澄清，原点节点具有很高的概率，距离最优估计器选择的节点的距离为3，其中距离是连接两个节点的唯一路径的边数。这通过原点和所选节点之间的距离的概率分布来阐明。

时尚和艺术周期受到精英

竞争的反主导信号的驱动：

音乐风格的定量证据

原文标题：

Fashion and art cycles are driven by counter-dominance signals of elite competition: quantitative evidence from music styles

地址：

http://arxiv.org/abs/1901.03114

作者：

Peter Klimek, Robert Kreuzbauer, Stefan Thurner

摘要： 艺术和时尚风格等人类象征系统来自复杂的社会过程，这些过程控制着现代社会的不断重组。它们提供了一种信号方案，允许精英成员区别于社会其他人。了解艺术和时尚周期动态的努力基于“自下而上”和“自上而下”的理论。根据“自上而下”理论，精英成员通过引入低地位群体采用的新符号（例如时尚风格）来表明其优越地位。为响应这种采用，精英成员需要引入新符号来表明其状态。根据许多“自下而上”的理论，风格周期从较低的阶级演变而来，并遵循基本上随机的模式。我们提出了一种基于反支配信号的替代解释。

在那里，精英成员希望其他人模仿他们的符号;只有当外来者通过引入与精英认可的信号形成对比的信号成功地挑战精英时，才会发生变化。我们使用动态网络方法对1956年至2015年间发布的包含近800万张音乐专辑的数据进行了调查。该网络系统地量化了竞争音乐风格及其随时间变化的艺术相似性。我们对当前精英成员（自上而下），随机性（自下而上）或外围群体通过反支配信号引入新符号进行实证检验。我们发现明显的证据表明反霸权信号驱动音乐风格的变化。这为一个关于时尚周期的潜在社会动态的本质的长达一个世纪的辩论提供了定量的，完全数据驱动的答案。

浪漫伴侣算法匹配

中的无政府状态价格

原文标题：

Price of Anarchy in Algorithmic Matching of Romantic Partners

地址：

http://arxiv.org/abs/1901.03192

作者：

Andrés Abeliuk, Khaled Elbassioni, Talal Rahwan, Manuel Cebrian, Iyad Rahwan

摘要： 算法匹配站点为用户提供了前所未有的潜在配合。然而，它们也构成了具有潜在道德风险的委托 – 代理问题。代理商的兴趣是最大限度地利用网站，而委托人的兴趣是找到最好的浪漫伴侣。这会产生利益冲突：最佳匹配用户将导致稳定的夫妻和使用该网站的单身人数减少，这对在线约会行业是不利的。在这里，我们借用博弈论中的无政府价格概念来量化由代理人的自身利益引起的在线交友网站社会效率的下降。我们得出了无政府状态的理论界限，表明它可以受一个不依赖于约会网站用户数量的常数的限制。

这表明随着在线约会网站的增长，它们的潜在利益可以在不牺牲社会效率的情况下扩大规模。此外，我们在匹配市场中进行涉及人类受试者的实验，并将通过最佳匹配服务实现的社会福利与自利益匹配算法进行比较。我们通过引入约会网站之间的竞争表明，代理人的自私行为与其用户一致，社会效率也在提高。

给定相关组件中

断的级联停电风险

原文标题：

Risk of Cascading Blackouts Given Correlated Component Outages

地址：

http://arxiv.org/abs/1901.03304

作者：

Laurence A. Clarfeld, Paul D.H. Hines, Eric M. Hernandez, Margaret J. Eppstein

摘要： 当电力系统中的N个组件中的k个几乎同时发生中断时，通常会发生级联停电，从而触发通过网络传播的后续故障并导致显著的负载减少。虽然大型瀑布很少，但它们的影响可能是灾难性的，因此量化风险对于电网规划和运营非常重要。在先前的量化这种风险的方法中的一个共同假设是，k个启动组件中断是统计上独立的事件。然而，当由共同的外部原因触发时，启动中断实际上可能是相关的。在这里，copula分析用于量化启动中断与级联故障风险的相关性的影响。

该方法在两个测试用例中进行了演示;波兰电网在不同负载条件下的2383总线型号以及基于美国西部地区的合成10,000总线型号。美国西部测试案例的大规模需要开发新方法，以限制对N-3停电造成的突发事件总数的估计。结果表明，级联失效的风险和高阶突发事件的相对贡献随着组件故障中空间相关性的增加而增加。