核心速递
-
网络上复发性流行病的流行传播者;
-
基于协同图划分的可扩展异构社会网络;
-
-
-
比较虚拟实验和实地考察中行人的绕过障碍物的路径选择行为;
-
利用Konig-Egervary层-子图的层次分解机制及其在顶点覆盖上的应用;
-
-
弥合社区和节点表示之间的鸿沟：基于社区检测的图嵌入;
-
基于非对称度Twitter图的子图分类、聚类与中心性研究;
-
基于网络的卫生服务区域划分：社区检测算法的比较分析;
-
-
-
-
BHIN2vec：异构信息网络中的关系类型的平衡;
-
-
-
-
-
-
-
-
完全图的Axelrod模型的Erdos-Renyi相变;
Influential spreaders for recurrent epidemics on networks
http://arxiv.org/abs/1912.08459
Gaël Poux-Médard, Romualdo Pastor-Satorras, Claudio Castellano
摘要：识别哪些节点是在网络上传播进程的最佳种子是一个有价值的问题，近年来，引起了人们的极大兴趣。虽然活动主要集中在非周期性的动力学类型上，但我们在这里考虑SIS模型，在该模型中，一个节点中播撒的爆发可引发一个有限活动雪崩。我们基于Larremore等人提出的网络雪崩理论框架，获得单个节点在流行病阈值以上和以下的影响范围（雪崩持续时间和雪崩大小）的详细定量预测。当该方法与退火网络近似相辅相成时，我们获得了接近于过渡的感兴趣的观测值的完全解析表达式，突出了度中心性的作用。本文将这些结果与在具有幂律度分布的合成网络上进行的数值模拟进行了比较，发现它们大体上是一致的，留下了一些有待进一步研究的问题。
Scalable Heterogeneous Social Network Alignment through Synergistic Graph Partition
http://arxiv.org/abs/1912.08372
Yuxiang Ren, Lin Meng, Jiawei Zhang
摘要：近年来，社会网络比对一直是社会网络分析的一个重要研究课题。通过确定网络上的共享用户，研究人员将有机会更全面地了解用户在网络内和网络间的社交活动。社交网络的整合是一个非常困难的问题。除了网络异构性带来的挑战外，网络同步问题还可以转化为一个具有极大搜索空间的组合优化问题。随着网络规模的增加，现有对准模型的学习效率将显著降低。本文将重点研究可扩展异构社会网络同步问题，提出一种新的两阶段网络对齐模型，即可扩展异构网络同步（SHNA）。基于一组网络内和网络间的元图，SHNA首先协同地将社会网络划分为一组子网络。通过部分已知的锚定链路，SHNA将提取被划分的子网对应关系。SHNA不需要同步完整的输入网络，而是提出识别匹配子网络对之间的锚链接，而对不匹配子网络对之间的锚链接进行剪枝，有效地缩小搜索空间。在一个真实的社交网络数据集上，我们做了大量的实验来比较SHNA和最新的基线方法。实验结果证明了SHNA模型在解决这一问题上的有效性和有效性。
Competitive Contagion with Sparse Seeding
http://arxiv.org/abs/1912.08243
Milad Siami, Amir Ajorlou, Ali Jadbabaie
摘要：本文研究了社会网络环境下的营销与产品定义策略模型。我们考虑两家生产可替代产品的公司，它们可以通过在市场中培育关键产品来提高市场份额。消费者更新两种产品的消费水平，作为对前一时期邻居消费的最佳反应。这将导致产品消耗的线性更新动力学。每个消费者从每个邻居的消费中获得外部性，而对于同一企业的产品的消费，外部性的强度更高。我们将上述背景描述为企业之间的双寡头博弈，并引入一个新的框架，允许稀疏播种作为均衡策略出现。然后研究了网络结构对最优播种策略的影响以及策略的稀疏程度。特别地，我们得到了在大种群中，近纳什均衡策略渐近导致稀疏播种的条件。
Multi-Channel Graph Convolutional Networks
http://arxiv.org/abs/1912.08306
Kaixiong Zhou, Qingquan Song, Xiao Huang, Daochen Zha, Na Zou, Xia Hu
摘要：图神经网络（GNN）在对图结构进行分类方面已被证明是有效的。为了进一步提高图形表示的学习能力，本文研究了分层GNN。它利用可分化池将节点集群到固定的组中，并生成一个粗粒度结构，并伴随着原始图的收缩。然而，这样的聚类会丢弃一些图信息，从而得到次优的结果。这是因为节点本身具有不同的特征或角色，并且两个非同构图可能具有相同的粗粒度结构，这些粗粒度结构在池化后无法区分。为了弥补粗粒度聚类带来的损失，进一步提高GNN的性能，我们提出了一种多通道图卷积网络（MuchGCN）。它是由卷积神经网络驱动的，在卷积神经网络中对一系列通道进行编码以保持输入图像的综合特性。因此，我们对特定的图卷积进行去噪，以学习每一层的一系列图通道，并迭代地汇集图以编码层次结构。为了证明MuchGCN算法相对于最新的图形分类算法的优越性，我们进行了大量的实验。
比较虚拟实验和实地考察中行
人的绕过障碍物的路径选择行为
Comparing the route-choice behavior of pedestrians around obstacles in a virtual experiment and a field study
http://arxiv.org/abs/1912.08432
Hongliu Li, Jun Zhang, Long Xia, Weiguo Song, Nikolai W.F. Bode
摘要：无论是在紧急情况下还是在日常生活中，行人通常需要在到达目的地的不同路线之间做出选择。这种路径反射行为在决定交通管理、疏散效率和建筑设计中具有重要意义。在此基础上，利用现场观测和虚拟实验，研究了行人在绕行出口障碍物时的路径选择行为，考察了三个因素的影响，即路径起点的局部距离。以及沿线的行人密度和步行速度。关键的是，现场研究和虚拟实验都考虑了相同的场景，这使得我们可以直接评估在虚拟环境中测试行人行为的有效性。我们发现，在两个数据集中，选择更紧密的出口路径的人的比例随着出口路径起始点之间的距离的增加而增加。在我们的数据中，行人的选择也取决于沿线的行人密度，人们更喜欢使用较少的路线。因此，我们的结果证实了先前建立的路径选择机制，我们可以根据这些因素预测超过74%的选择。现场研究和虚拟实验结果的定性一致性表明，在简单的路径选择场景中，如本文所研究的场景，虚拟实验可以成为研究行人行为的有效实验技术。因此，我们为虚拟环境中新兴的实验范式提供了急需的经验支持。
利用Konig-Egervary
层-子图的层次分解机制
及其在顶点覆盖上的应用
Hierarchical Decomposition Mechanism by K”{o}nig-Eg’{e}rvary Layer-Subgraph with Application on Vertex-Cover
http://arxiv.org/abs/1912.08559
Xiangnan Feng, Wei Wei, Jiannan Wang, Xue Liu, Zhiming Zheng
摘要：Konig-Egervary（KE）图和定理为图论提供了有用的工具和深刻的理解，而图论是建立复杂系统模型的重要途径。KE性质与最大匹配问题和最小顶点覆盖问题密切相关，在许多数学、物理和计算机科学问题中得到了广泛的研究和应用。本文根据KE图的结构特点和最大边匹配的应用，提出了一般图的KE层结构的概念，将图分解为若干层。为了实现层次分解，通过顶点覆盖的解空间表达式给出了KE图的验证算法，并说明和证明了多级KE图与最大匹配的关系。此外，还提出了一种计算KE层数目和近似最小顶点覆盖的框架，并采用不同的节点切换策略和计数能量策略。本文研究了不同KE层之间的相变现象，利用该策略得到的顶点覆盖数与其他几种方法相比具有可比性，其效率优于过渡点之前的现有方法。此外，所提出的方法在不同尺度上执行稳定性和满足精度以近似精确的最小覆盖。KE层分析为更好地理解图的结构组织提供了一个新的视角，其形成机制有助于揭示大规模图形/系统识别的内在复杂性，并建立启发式策略。
Inferring the causal effect of journals on citations
http://arxiv.org/abs/1912.08648
摘要：根据定义，高影响力期刊上的文章平均被引用率更高。但他们被引用的频率更高，是因为这些文章在某种程度上“更好”了，还是仅仅因为它们出现在一篇影响很大的新闻中，尽管有证据表明最近的因果关系并不清楚。但我们在此将已发表期刊文章的引文与其预印本的引文进行比较，以揭示其因果机制。我们的模型建立在早期模型的基础上，来推断期刊对引文的因果效应。我们找到了两种影响的证据，研究发现，高影响力的期刊似乎选择的文章往往会吸引更多的引用。同时，我们发现高影响力期刊增加了已发表文章的被引用率。我们的研究结果加深了对期刊在研究体系中作用的理解。近年来，在研究评估中使用期刊指标越来越受到批评，文章级的引用有时被认为是一种替代方法。研究结果表明，从评价中剔除影响因素并不能消除期刊的影响力。这一观点对研究评价实践的变革具有重要的启示。
弥合社区和节点表示之间的
鸿沟：基于社区检测的图嵌入
Bridging the Gap between Community and Node Representations: Graph Embedding via Community Detection
http://arxiv.org/abs/1912.08808
Artem Lutov, Dingqi Yang, Philippe Cudré-Mauroux
摘要：图嵌入已成为许多数据挖掘和分析系统的关键组成部分。当前的图形嵌入方法要么从图中采样大量的节点对，要么通过随机优化来学习节点嵌入，或者通过计算密集矩阵分解技术分解高阶节点邻接矩阵。这些方法通常需要大量的资源用于学习过程，并且依赖于多个参数，这限制了它们在实践中的适用性。此外，大多数现有的图形嵌入技术仅在一个特定的度量空间中有效地操作（例如，用余弦相似度产生的），不保留输入图的高阶结构特征，并且不能自动确定嵌入空间中有意义的维数。通常，生成的嵌入不容易解释，这会使分析进一步的复杂化并限制其适用性。为了解决这些问题，我们提出了一种高效的、无参数的图嵌入技术DAOR，它可以在不需要任何人工调整的情况下生成度量空间健壮、紧凑和可解释的嵌入。与十几个最先进的图形嵌入算法相比，DAOR在两个节点分类（有利于形成高阶邻近度）和链路预测（这主要依赖于低阶邻近度）上产生了竞争性的结果。然而，与现有技术不同，DAOR不需要任何参数调整，并且将嵌入生成速度提高几个数量级。因此，我们的方法的目标是大大简化和加快涉及图形表示学习的数据分析任务。
基于非对称度Twitter图
的子图分类、聚类与中心性研究
Subgraph Classification, Clustering and Centrality for a Degree Asymmetric Twitter Based Graph Case Study: Suicidality
http://arxiv.org/abs/1912.08909
Keith Andrew, Eric Steinfelds, Karla M. Andrew, Kay Opalenik
摘要：本文利用NodeXL的工具和分析特性，对一个应用于度非对称顶点图集的社会化媒体数据采集和可视化进行了初步的研究。我们考虑Twitter上收集的与自杀意念、自杀未遂、自残和欺凌有关的图表。虽然Twitter sphere只捕获了一个小的、带有年龄偏见的通信样本，但它是一个现成的公共数据库，可用于产生大量样本集的丰富主题。所有这些主题都产生了高度非对称的顶点度网络，并且都具有相同的一般拓扑特征。总体上，平均全局聚类系数为0.038，图聚类密度为0.00034，Clauset Newman Moore分组的最大测地线距离为6。特征向量的中心性没有给出任何大的中心影响点，介数中心性显示了许多桥接点，表明了稀疏的社区结构。在显著性大于1的词和词对中，词类情感得分呈现出显著负分的不对称性。我们使用了一个恶作剧分析来检查Twitter机器人故意在这些话题上的错误信息。
基于网络的卫生服务区域划分：
社区检测算法的比较分析
Network-Based Delineation of Health Service Areas: A Comparative Analysis of Community Detection Algorithms
http://arxiv.org/abs/1912.08921
Diego Pinheiro, Ryan Hartman, Erick Romero, Ronaldo Menezes, Martin Cadeiras
摘要：卫生服务区（HSA）是由类似的卫生保健设施服务的一组地理区域。HSA的划分在确定某一地区的医疗服务特征方面发挥着关键作用，从而能够更好地规划和管理医疗服务。尽管达特茅斯HSA已成为几十年来的标准描述，但最近的工作表明，使用基于网络的方法改进了HSA描述，其中HSA是由Louvain算法在医院患者出院网络中提取的社区。考虑到现有的社区检测算法所提取的社区存在的异质性，缺乏对最优HSA划界的社区检测算法的比较分析。在这项工作中，我们使用一个包含美国7年内不同类型住院病人出院的大规模数据集，比较了社区检测算法产生的HSA描绘。我们的结果复制了以往研究中发现的群落检测算法之间的异质性，以及基于网络的HSA划分方法的改进，并认为Infomap可能是一种更适合于HSA划分的群落检测方法，因为它需要具有高定位指数和低网络电导的大量HSA。
Real-time 2019 Portuguese Parliament Election Results Dataset
http://arxiv.org/abs/1912.08922
摘要：本文提供了一组数据，描述了葡萄牙2019年10月6日跨越4小时25分钟的议会选举结果的演变。这些数据的时间间隔5分钟，涉及参与选举活动的27个政党的结果。数据集是为预测建模任务定制的，主要集中在数值预测任务上。此外，它允许其他任务，如顺序回归或学习排名。
Dense graphs with scale-free feature
http://arxiv.org/abs/1912.08923
Fei Ma, Xiaomin Wang, Ping Wang, Xudong Luo
摘要：复杂网络代表着各种复杂系统，近年来受到了科学界广泛的关注。无标度特性和小世界特性在大量复杂网络中得到了广泛的观察。虽然已有研究表明，所有无标度网络都是稀疏的，但是存在一些真实的网络，例如，社交网络、城市网络、信息网络，观察发现它们是密集的。为了了解这些网络的动力学和结构，最近花费了大量的精力，因此发展了许多技术。相比之下，本文从图论出发，提出了一种基于一阶细分和线性运算的无标度稠密图生成框架。分析和数值验证表明，我们的方法比那些已有方法更高效。从理论上讲，我们的方法不仅可以用来生成幂律指数为介于1与2之间的理想无标度图，而且还可以用来建立出乎意料的网络模型来反驳一些广为人知的说法，如Cohen等人提出的无标度网络是超小的。
The Iterated Local Directed Transitivity Model for Social Networks
http://arxiv.org/abs/1912.08924
Anthony Bonato, Dan W. Cranston, Melissa Huggan, Trent Marbach, Raja Mutharasan
摘要：基于三元组的传递性，我们提出了一种新的社会网络有向图模型。在迭代局部有向传递（ILDT）模型中，新节点是在离散时间步长上产生的，并继承父节点的链接结构。ILDT模型可以看作是引入无向图的ILT模型的有向模拟。本文研究了网络科学和ILDT有向图的图论性质，并证明了ILDT模型具有密度幂律，使得模型生成的有向图随时间而密度化。本文研究了有向三元数，给出了有向三元数和传递三元数的计数。ILDT模型在现实社会网络中产生了更多的传递。在所选择的初始有向图实例中，该模型最终生成具有哈密顿有向环图。我们讨论了ILDT有向图的邻接矩阵的特征值，并给出了进一步的研究方向。
BHIN2vec：异构信息
网络中的关系类型的平衡
BHIN2vec: Balancing the Type of Relation in Heterogeneous Information Network
http://arxiv.org/abs/1912.08925
Seonghyeon Lee, Chanyoung Park, Hwanjo Yu
摘要：网络嵌入的目的是将网络中的节点转化为低维的嵌入向量。近年来，异构网络在表示数据中的各种信息方面显示出了其优越性。然而，异构网络的嵌入从不平衡性问题，即关系类型的大小（或网络中与类型相关的边的数目）上得到了不平衡。本文提出了一种新的异构网络嵌入方法BHIN2vec，它考虑了网络中所有关系类型之间的平衡。我们将异构网络嵌入视为同时解决多个任务，其中每个任务对应于网络中的每个关系类型。在将跳转丢包分解为对应于不同任务的多个丢包后，我们提出了一种新的随机游走策略，通过考虑相对训练率来聚焦于丢包值较高的任务。与以往的随机游走策略不同，本文提出的随机游走策略根据不同任务间的相对训练率生成训练样本，从而实现了节点嵌入的均衡训练。我们在节点分类和推荐方面的大量实验证明了BHIN2vec相对于最新方法的优越性。同时，基于相对训练率，分析了嵌入空间中各关系类型的表示量。
Rumor Detection and Classification for Twitter Data
http://arxiv.org/abs/1912.08926
Sardar Hamidian, Mona T Diab
摘要：随着在线媒体数据作为信息源的普及，在微博社交媒体的语境中，谣言的散布与传播是常见的问题。在这项研究中，我们讨论的微博社交媒体的范围内两个常见的问题，我们使用标准数据集探索问题，并设计出新的特征，以研究它们对任务的影响。
Hyperbolic Multiplex Network Embedding with Maps of Random Walk
http://arxiv.org/abs/1912.08927
摘要：最近关于双曲空间中网络嵌入的研究已经在一些应用中证明是成功的。然而，现实网络中的节点往往通过几个不同的通道进行交互。简单的聚合或不知道这种复用将导致错误的结果。另一方面，节点间的交互模式存在冗余信息。最近的研究揭示了群落结构与双曲线坐标之间的相似性。为了在降低复用网络冗余度的同时了解各节点的有效嵌入表示，本文提出了一种将复用双曲网络嵌入和复用社区检测相结合的统一框架。直观的理论基础是，高阶节点嵌入方法有望缓解观测网络的稀疏和噪声结构，这将有助于社区检测任务的完成。相反，改进的社区结构也将指导节点嵌入任务。为了在保留特征的同时融合信道间的共同特征，本文提出了一种在潜在的多重双曲空间中遍历的随机游走方法来检测信道间的社区，并将节点嵌入与社区检测联系起来。利用不同的真实世界数据集对该框架进行了多个网络任务的评估。结果表明，与现有方法相比，我们的框架是有效的。
Early Detection of Research Trends
http://arxiv.org/abs/1912.08928
摘要：对于许多利益相关者来说，能够迅速识别新的研究趋势是战略性的，包括大学、资助机构、学术出版商和公司。这些文献提出了几种方法来确定新的研究课题的出现，这些方法依赖于这样一个假设，即该课题已经显示出一定程度的受欢迎程度，并且一直被一个研究群体所引用。然而，在一个研究群体始终如一地给这个主题贴上标签并与一些出版物联系起来之前，在一个萌芽阶段发现一个新的研究领域，仍然是一个公开的挑战。在这篇论文中，我们开始通过研究新课题产生之前的动力来应对这一挑战。研究表明，一个新课题的出现是由相关研究领域之间合作的步伐明显加快所预期的，可以看作是这个新课题的始祖。基于这一认识，我们开发了Augur，这是一种新的方法，可以客观地检测新研究课题的出现。Augur分析了研究领域之间的历时关系，能够发现与新的研究主题的出现相关的动态主题群。在此，我们还提出了一种新的社区检测算法——高级团渗滤法（ACPM）。Augur在2000-2011年的时间框架内被评为1408个新主题的金标准，在精确性和召回率方面都优于四种替代方法。
PFaRA: a Platoon Forming and Routing Algorithm for Same-Day Deliveries
http://arxiv.org/abs/1912.08929
Sînziana-Maria Sebe, Jörg P. Müller
摘要：队列，指的是作为一个整体紧密地行驶在一起的车辆，承诺改善高速公路和城市道路上的道路使用。我们研究了城市环境中同一天交货情况下的队列。多个自利物流服务提供商（LSP）通过部署能够组建和成排行驶的自主电动汽车来执行当天交货。在我们的研究中，我们考虑的一个新的方面是车队的异质性，即车辆装备有不同的能力和约束，并且属于不同的供应商。我们的目标是研究这些排是如何形成的，以及它们的潜在属性和好处。我们提出了一种队列和路由算法，称为PFARA，它在考虑车辆偏好和约束的同时，为多辆车找到最长的公共路径。PFARA由速度聚类和线性优化两部分组成。为了测试该方法，我们使用了一个模拟，使用真实的城市网络数据和背景交通模型。结果表明，该方法的性能与简单的路径匹配方法相当，但可以提高车辆的利用率，并扩展LSP。我们证明了所提供的分组是可行的，并为所有参与排的车辆提供了好处。
Graphlets in Multiplex Networks
http://arxiv.org/abs/1912.08930
Tamara Dimitrova, Kristijan Petrovski, Ljupco Kocarev
摘要：我们开发了多重网络的基本单元分析，并讨论了如何将此分析扩展到多层和多级网络以及具有节点或链接类别属性的图上。该分析已适用于两个典型的多路复用示例：以957-PLEX网络表示的经济贸易数据和以12-PLEX网络表示的75个社会网络。我们发现楔块（开放三位一体）在经济贸易网络中比在社会网络中出现的频率更高，这表明一个国家倾向于在非封闭三位一体的地方结构中生产并贸易一种产品。此外，我们的分析还提供了证据，表明多样性小的国家往往会形成相关的三角形。楔形也出现在社交网络中，但是社交网络中的主要笔迹是三角形（闭合的三元组）。如果多重结构表示一个强连接，那么笔迹分析为强/弱连接和结构孔的概念提供了另一个证据。与Granovetter关于弱关系强度的开创性研究相比，在文献中，只有强关系的楔形是不存在的，然而，我们研究表明，在分析的75个社交网络中，只有强关系的楔形不仅存在而且显著相关。
Impact of Traffic Conditions and Carpool Lane Availability on Peer to Peer Ridesharing Demand
http://arxiv.org/abs/1912.08931
Sara Masoud, Young Jun Son, Neda Masoud, Jay Jayakrishnan
摘要：一个点对点乘车共享系统将使用个人车辆的驾驶员与寻找乘车的乘客连接起来，进行日常活动。一个设计良好、实施得当的乘车共享系统可以带来社会效益，如缓解拥堵及其对环境的不利影响，以及缩短出行时间和为相关个人节省资金方面的个人效益。本文采用基于多主体的仿真模型，研究拼车专用道的可用性和交通状况对拼车需求的影响。主体可以选择使用他们的私人车辆，或参与共享系统，采用一种精确的多对多乘车匹配算法，即每个驾驶员可以上下多个乘客，每个乘客可以通过多辆车之间的换乘来完成自己的行程。所提出的方法在AnyLogic ABS软件中实现，并基于加利福尼亚州洛杉矶市的实际旅行数据集进行验证。这项研究的结果将有助于了解城市环境的类型，这些类型将更容易接受共享乘车服务。
An Adaptive Similarity Measure to Tune Trust Influence in Memory-Based Collaborative Filtering
http://arxiv.org/abs/1912.08934
Mohammad Reza Zarei, Mohammad R. Moosavi
摘要：推荐系统的目的是为每个用户提供相关的和潜在的有趣的信息。这是通过利用相似用户已经记录的趋势或检测与用户感兴趣的项目相似的项目来实现的。最近的研究已经解决了数据稀疏和冷启动问题等挑战。利用社会信息不仅提高了预测精度，而且解决了数据稀疏性的难题。本文研究了在基于内存的协同过滤推荐系统中使用直接和间接信任信息的影响。本文提出了一种自适应相似性度量方法，并利用贪婪和基于梯度的优化两种学习方案来调整社会信息的贡献。在两个真实世界的数据集Epinions和FilmTrust上，将该方法的结果与目前最先进的基于记忆和基于模型的CF方法进行了比较。实验表明，该方法对设计一个准确、全面的推荐系统是非常有效的。
完全图的Axelrod模型
的Erdos-Renyi相变
An Erdos-Renyi phase transition in the Axelrod model on complete graphs
http://arxiv.org/abs/1912.09420
Sebastián Pinto, Pablo Balenzuela
摘要：Axelrod模型自提出社会影响和文化传播以来，得到了广泛的研究。特别是，统计物理界关注的是相变的存在作为其两个主要参数F和Q的函数。在这项工作中，我们证明了Axelrod模型在F的极限下经历了二阶相变。当用初始状态下的相互作用概率来描述时，这个跃迁等价于随机网络中的ER相变，它依赖于F和Q之间的标度关系。我们还发现，这个概率在稀疏网络中通过折叠不同状态下的跃迁曲线参数F的值，起着关键作用。
声明：Arxiv文章摘要版权归论文原作者所有，由本人进行翻译整理，未经同意请勿随意转载。本系列在微信公众号“网络科学研究速递”（微信号netsci）和个人博客 https://www.complexly.me （提供RSS订阅）进行同步更新。
网络嵌入综述 | 网络科学论文速递23篇
个体科研合作中的合著网络和劳动分工 | 网络科学论文速递21篇
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧!
