核心速递

多层网络中的核分解：理论、算法和应用;
随机游走者在无标度网络上访问的节点不同;
受访者驱动抽样中的渐近种子偏差;
通过估计块转移概率减少受访者驱动采样中的种子偏差;
出版物的中介性;
利用社交媒体分析提升旅游领域决策能力;
社会网络层次识别研究综述;

多层网络中的核分解：

理论、算法和应用

原文标题：

Core Decomposition in Multilayer Networks: Theory, Algorithms, and Applications

地址：

http://arxiv.org/abs/1812.08712

作者：

Edoardo Galimberti, Francesco Bonchi, Francesco Gullo, Tommaso Lanciano

摘要：多层网络是模拟复杂系统的强大范例，其中可能在同一组实体之间发生各种关系。尽管对这种类型的网络中的各种问题，算法和分析方法非常感兴趣，但是提取密集子图的问题仍然很大程度上未被探索。作为这个方向的第一步，我们研究了多层网络的核心分解问题。

与核心全部彼此嵌套的单层对应物不同，在多层上下文中，多层核心之间不存在总排序：它们形成晶格，其大小在层数中是指数的。在这个设置中，我们设计了三种算法，这些算法在访问核心点阵和修剪技术方面有所不同。我们在各种各样的真实多层网络上评估三种算法的时间和空间效率。然后，我们研究了仅提取最内核的问题，即，在所有层上的索引方面，不受任何其他核心支配的核心。由于内部核心的数量级比所有核心都要小，因此需要开发能够有效利用最大性属性并直接提取最内核的算法，而无需先计算完整的分解。

此外，我们展示了多层核心分解工具在多层网络中提取密集子图的问题。我们介绍了多层最密集子图的定义，它在高密度和高密度层数之间进行折衷，并说明如何利用多层芯分解来质量保证来近似这个问题。我们还利用多层核心分解来加速频繁交叉图准集团的提取，并将社区搜索问题推广到多层设置。

随机游走者在无标度

网络上访问的节点不同

原文标题：

Distinct nodes visited by random walkers on scale-free networks

地址：

http://arxiv.org/abs/1501.01246

作者：

Aanjaneya Kumar, M. S. Santhanam

摘要： 离散格子上的随机游走是基本模型，它们构成了我们理解运输和扩散过程的基础。对于复杂网络上的单个随机游走者，已知许多属性，例如平均首次通过时间和覆盖时间。然而，诸如搜索引擎和推荐系统的许多最近的应用涉及复杂网络上的多个随机游走者。

在这项工作中，基于数值模拟，我们表明， W 随机游走者在时间 t 中没有访问的无标度网络的节点部分具有拉伸的指数形式，与网络的细节和步行者的数量无关。这导致 W 步行者未访问的节点与时间 t 内的一个步行者之间的幂律关系。有效地，找到由 W 步行者访问的不同节点的问题可以减少到单个步行者的问题。通过在近似显示无标度结构的四个不同的真实网络上验证它们来证明结果的稳健性。

受访者驱动抽样

中的渐近种子偏差

原文标题：

Asymptotic Seed Bias in Respondent-driven Sampling

地址：

http://arxiv.org/abs/1808.10593

作者：

Yuling Yan, Bret Hanlon, Sebastien Roch, Karl Rohe

摘要： 受访者驱动的抽样（RDS）通过激励抽样的个体将其联系人引入样本来收集网络人群中的个体样本。该迭代过程从一些种子节点初始化。有时，这种选择会产生大量的种子偏差。其他时候，种子偏差很小。

本文通过表征其对各种RDS估计量的限制分布的影响，对这种偏差有了更深刻的理解。使用经典工具和多类型分支过程的结果（Kesten和Stigum，1966），我们证明了种子偏差对于广义最小二乘（GLS）估计可以忽略不计，对于逆概率加权和Volz-Heckathorn都是不可忽略的。（VH）估计。

特别地，我们显示（i）高于临界阈值，VH收敛到非平凡的混合物分布，其中混合物组分取决于种子节点，并且混合物分布可能是多模态的。此外，（ii）在马尔可夫过程的一定条件下，GLS收敛于独立于种子节点的高斯分布。模拟数据和经验社会网络的数值实验表明，这些结果似乎超出了定理的马尔可夫条件。

通过估计块转移概率减少

受访者驱动采样中的种子偏差

原文标题：

Reducing Seed Bias in Respondent-Driven Sampling by Estimating Block Transition Probabilities

地址：

http://arxiv.org/abs/1812.01188

作者：

Yilin Zhang, Karl Rohe, Sebastien Roch

摘要： 受访者驱动的抽样（RDS）是研究边化或难以接触的人群的流行方法。它通过激励参与者将他们的朋友推荐到研究中来收集来自网络人群的样本。分析RDS样品的一个主要挑战是种子偏差。种子偏见指的是当社会网络被划分为多个社区（或区块）时，RDS样本可能无法提供人口中不同社区的均衡表示，并且这种不平衡与初始参与者（或种子）。

在这种情况下，估计量的分布通常是非平凡的混合，其由（1）种子确定，（2）推荐如何从一个块转换到另一个块。本文表明（1）块转移概率易于高精度估计，（2）我们可以使用这些估计的块转移概率来估计块上的平稳分布，从而估计块比例。这种块上的静态分布先前已用于RDS文献中，以评估采样过程是否已“混合”。我们在简单的后分层（PS）估计中使用这些估计的块比例，这大大减少了种子偏差。

通过以这种方式聚合块/层，我们证明PS估计量是 sqrt {n} – 在马尔可夫模型下是一致的，即使其他估计量不是。仿真表明，与最先进的估计器相比，PS估计器具有更小的均方根误差（RMSE）。

出版物的中介性

原文标题：

Intermediacy of publications

地址：

http://arxiv.org/abs/1812.08259

作者：

Lovro Šubelj, Ludo Waltman, Vincent Traag, Nees Jan van Eck

摘要： 科学出版物的引文网络提供了对科学知识结构和发展的基本见解。我们提出了一种新的措施，称为中介，用于追踪科学知识的历史发展。鉴于两种出版物，一种较旧的和较新的出版物，中介性确定了从较旧的出版物到最近的出版物在历史发展中起主要作用的出版物。已确定的出版物对于连接引文网络中较旧和较新的出版物非常重要。

在提供了介数中心性的正式定义之后，我们研究了它的数学性质。然后，我们提出了两个实证案例研究，一个是在社区检测和科学计量学文献之间的界面上追踪历史发展，另一个是检查同行评审文献的发展。我们从数学和经验上展示了介数中心性与主要路径分析的不同之处，主要路径分析是追踪引文网络历史发展的最常用方法。主要路径分析往往倾向于较长路径而不是较短路径，而中间路径具有相反趋势。与主要路径分析相比，我们得出结论，中介为追踪科学知识的历史发展提供了更有原则的方法。

利用社交媒体分析

提升旅游领域决策能力

原文标题：

Enhancing Decision Making Capacity in Tourism Domain Using Social Media Analytics

地址：

http://arxiv.org/abs/1812.08330

作者：

Supun Abeysinghe, Isura Manchanayake, Chamod Samarajeewa, Prabod Rathnayaka, Malaka J. Walpola, Rashmika Nawaratne, Tharindu Bandaragoda, Damminda Alahakoon

摘要： 社交媒体在过去十年中获得了极大的欢迎。人们倾向于自由地表达他们在社交媒体上的日常遭遇。这些日常遭遇包括他们旅行的地方，他们尝试的酒店或餐馆以及与旅游相关的方面。由于人们通常在社交媒体上表达他们的真实经历，所表达的意见包含有价值的信息，可用于产生商业价值和协助决策过程。由于数据量很大，手动浏览每个项目并提取信息并不是一个可行的任务。

因此，我们提出了一种社交媒体分析平台，该平台能够使用机器学习技术和可视化工具识别讨论途径和方面及其相应的情感和更深层的情感，该工具以可理解和简洁的方式显示所提取的见解。确定的主题路径和方面将使决策者能够深入了解关于实体的讨论最多的主题，而相关的情绪和情感将有助于识别反馈。

社会网络层次识别研究综述

原文标题：

A Survey of Hierarchy Identification in Social Networks

地址：

http://arxiv.org/abs/1812.08425

作者：

Denys Katerenchuk

摘要： 人类本质上是社会性的。纵观历史，人们已经形成了社区并建立了关系。与同事，朋友和家人的大多数关系都是在面对面的互动中发展起来的。这些关系是通过明确的通信手段建立的，例如单词和隐含的语调，如语调，肢体语言等。通过分析人类交互，我们可以得出关于对话参与者之间的关系和影响的信息。然而，随着互联网的发展，人们开始通过在线社会网络中的文本进行交流。有趣的是，他们将他们的交际习惯带到了互联网上。

许多社会网络用户彼此建立关系，并与领导者和追随者建立社区。认识到这些等级关系是一项重要任务，因为它将有助于了解社会网络并预测未来趋势，改进建议，更好地定位广告，并通过识别匿名恐怖组织的领导者来改善国家安全。在这项工作中，我概述了该领域的当前研究，并介绍了处理社会网络中识别等级关系问题的最先进方法。