原文标题: Attributed Graph Modeling with Vertex Replacement Grammars
地址: http://arxiv.org/abs/2110.06410
作者: Satyaki Sikdar, Neil Shah, Tim Weninger
摘要: 最近在形式语言理论和图论的交叉点上的工作探索了用于图建模的图文法。然而,现有的模型和形式主义只能在同构(即无类型或无属性)图上运行。我们放宽了这个限制并引入了属性顶点替换语法(AvrG),它可以有效地从异构(即类型、彩色或属性)图中提取。与当前最先进的方法在复杂的深度神经架构上训练大量模型不同,AVRG 模型是无监督且可解释的。它基于上下文无关的字符串语法,并通过将图重写规则编码为包含图元和有关它们如何组合在一起的说明的图文法来工作。我们表明 AVRG 可以编码输入图的简洁模型,同时忠实地保留它们的结构和分类属性。在大型真实世界数据集上的实验表明,从 AVRG 模型生成的图展示了与输入网络中发现的那些相匹配的子结构和属性配置。
分布式动态图中的增量社区检测原文标题: Incremental Community Detection in Distributed Dynamic Graph
地址: http://arxiv.org/abs/2110.06311
作者: Tariq Abughofa, Ahmed A.Harby, Haruna Isah, Farhana Zulkernine
摘要: 社区检测是图分析中的一个重要研究课题,具有广泛的应用。过去几年开发了各种静态社区检测算法和质量指标。然而,大多数现实世界的图都不是静态的,并且经常随着时间的推移而变化。在流数据的情况下,关联图中的社区需要不断更新,或者每当新数据流添加到图中时,这对设计良好的社区检测算法以维护流数据上的动态图提出了更大的挑战。在本文中,我们提出了一种增量社区检测算法,用于维护流数据上的动态图。本研究的贡献包括 (a) 分布式加权社区聚类 (DWCC) 算法的实现,(b) 新型增量分布式加权社区聚类 (IDWCC) 算法的设计和实现,以及 (c) 一项实验研究比较我们的 IDWCC 算法与 DWCC 算法的性能。我们验证了我们的框架在处理流数据和执行大型内存分布式动态图分析方面的功能和效率。结果表明,对于类似的精度,我们的 IDWCC 算法的执行速度比 DWCC 算法快三倍。
单元复形上的信号处理原文标题: Signal Processing on cell Complexes
地址: http://arxiv.org/abs/2110.05614
作者: T. Mitchell Roddenberry, michael T. Schaub, Mustafa Hajij
摘要: 在过去几年中,非欧域支持的信号处理引起了极大的兴趣。到目前为止,这种非欧几里得域主要被抽象为在节点上支持信号的图,尽管最近也考虑了在更一般的结构(例如单纯复形)上处理信号。在本文中,我们介绍了(抽象)规则单元复合体上的信号处理,它提供了一个统一的框架,包括图、单纯复合体、立方复合体和各种网格作为特殊情况。我们讨论如何推导出适用于这些细胞复合物的霍奇拉普拉斯算子。这些霍奇拉普拉斯算子能够构建卷积滤波器,通过定义在细胞复合体上的神经网络,可以将其用于线性过滤和非线性过滤。
SSSNET:半监督符号网络聚类原文标题: SSSNET: Semi-Supervised Signed Network Clustering
地址: http://arxiv.org/abs/2110.06623
作者: Yixuan He, Gesine Reinert, Songchao Wang, Mihai Cucuringu
摘要: 节点嵌入是分析网络的强大工具;然而,它们在节点集群这一重要任务中的全部潜力尚未得到充分利用。特别是,大多数最先进的生成有符号网络节点嵌入的方法都侧重于链接符号预测,而那些与节点聚类相关的方法通常不是图神经网络 (GNN) 方法。在这里,我们为半监督符号网络聚类的 GNN 框架中的训练节点引入了一种新的概率平衡归一化切割损失,称为 SSSNET。该方法端到端地结合了嵌入生成和聚类,没有中间步骤;它以节点聚类为主要焦点,重点是网络中出现的极化效应。我们方法的主要新颖之处在于对社会平衡理论在符号网络嵌入中的作用进行了新的探讨。证明嵌入标准合理的标准启发式取决于“敌人的敌人是朋友”的假设。相反,这里对敌人的敌人是否是朋友采取中立立场。在各种数据集上的实验结果,包括合成的带符号随机块模型、它的极化版本以及不同尺度的真实世界数据,表明 SSSNET 可以获得与最先进的谱聚类方法相当或更好的结果,适用于广泛的噪声和稀疏水平。 SSSNET 通过以节点级特征或标签的形式包含外生信息的可能性来补充现有方法。
使用用户移动性表征和建模应用程序对开源用户活动跟踪的综述原文标题: A Survey of Open Source User activity Traces with applications to User Mobility characterization and Modeling
地址: http://arxiv.org/abs/2110.06382
作者: Sinjoni Mukhopadhyay King, Faisal Nawab, Katia Obraczka
摘要: 当前最先进的用户移动研究广泛依赖于通过各种通信技术从行人和车辆活动中刻画的开源移动轨迹,因为用户参与了广泛的应用,包括互联医疗、本地化、社交媒体、电子商务等。这些痕迹中的大多数都具有丰富和多样的特征,不仅体现在它们提供的信息上,还体现在它们的使用和利用方式上。这种多样性给希望利用可用移动数据集的研究人员和从业人员带来了两个主要挑战。首先,如果不花大量时间查找,就很难鸟瞰可用轨迹。其次,一旦他们找到了踪迹,他们仍然需要弄清楚这些踪迹是否足以满足他们的需求。本次调查的目的有三个。它提出了一种分类法来对开源移动轨迹进行分类,包括它们的移动模式、数据源和收集技术。然后使用提议的分类法对现有的开源移动轨迹进行分类,最后,使用流行的公开可用数据集突出显示三个案例研究,以展示我们的分类法如何梳理轨迹中的特征集,以帮助确定它们对特定用例的适用性。
在接触网络上进行部分传播和社交距离的疫苗接种原文标题: Vaccination with partial transmission and social distancing on contact networks
地址: http://arxiv.org/abs/2110.06616
作者: Christian John Hurry, Alexander Mozeika, Alessia Annibale
摘要: 我们使用统计物理学的空腔方法研究疫苗接种对通过结构化网络传播的流行病风险的影响。我们放宽了疫苗接种可以防止先前研究中使用的疾病的所有传播的假设,因此接种疫苗的节点传播的可能性很小。为此,我们将空腔方法扩展到研究节点具有异构传输性的网络。我们发现部分传播的疫苗接种仍然提供群体免疫,并表明群体免疫阈值如何取决于不同传播性节点之间的分类性。此外,我们通过键渗透研究了社会疏远的影响,并表明以高传播性节点之间的链接为目标的渗透可以比以高传播性节点之间的链接为目标降低流行病的风险。最后,我们扩展了最近的方法来计算具有异质传播性的人群的风险分布方程,并通过比较节点和链接删除的随机和有针对性策略的影响,展示有针对性的社会疏远措施如何比无针对性的疫苗接种活动降低更大的总体风险。风险分布。
Facebook上独一无二:使用非 PII 数据(微)针对个人用户的制定和证据原文标题: Unique on Facebook: formulation and Evidence of (Nano)targeting Individual Users with non-PII data
地址: http://arxiv.org/abs/2110.06636
作者: José González-Cabañas, Ángel Cuevas, Rubén Cuevas, Juan López-Fernández, David García
摘要: 个人的隐私受到第三方透露其身份的能力的限制。某些数据项(例如护照 ID 或移动电话号码)可用于唯一标识一个人。这些被称为个人身份信息 (PII) 项目。先前的文献还报告说,在包含数百万用户的数据集中,几个非 PII 项目的组合(仅此不足以识别个人)可以唯一地识别数据集中的个人。在本文中,我们定义了一个数据驱动模型来量化用户的兴趣数量,这些兴趣使他们在 Facebook 上独一无二。据我们所知,这是对世界人口规模上个人独特性的首次研究。此外,用户的兴趣是可操作的非 PII 项目,可用于定义广告活动并向 Facebook 用户提供量身定制的广告。我们通过针对本文三位作者的 21 个 Facebook 广告活动进行了一项实验,以证明如果广告商理解用户的足够兴趣,则可以系统地利用 Facebook 广告平台专门向特定用户投放广告。我们将这种做法称为纳米靶向。最后,我们讨论了与纳米目标相关的有害风险,例如心理说服、用户操纵或勒索,并提供易于实施的对策,以防止基于 Facebook 纳米目标活动的攻击。
gitHub 中的技能多样性和集体智慧原文标题: Diversity of Skills and Collective Intelligence in GitHub
地址: http://arxiv.org/abs/2110.06725
作者: Dorota Celińska-Kopczyńska
摘要: 一个普遍的假设表明,个人倾向于与与他们相似的其他人一起工作。然而,对团队合作和团队解决复杂问题能力的研究表明,多样性在协作过程中起着至关重要的作用,有助于信息的传播。在本文中,我们调查了开源社区中 GitHub 用户之间的联系背后的模式。为此,我们使用社会网络分析和自组织映射作为相似性度量。对文本工件的分析揭示了这些连接的作用。我们发现,技能的多样性在交换信息(例如,在问题、评论和关注网络中)的用户之间创建链接方面起着至关重要的作用。与实际编码相关的网络连接是在具有相似特征的用户之间建立的。与存储库所有者不同的用户比类似的用户更频繁地报告错误、问题和寻求帮助。
出租车路线行驶距离和时间变化的尺度原文标题: Scaling of variations in traveling distances and times of taxi routes
地址: http://arxiv.org/abs/2110.06784
作者: Xiaoyan Feng, Huijun Sun, Bnaya Gross, Jianjun Wu, Daqing Li, Xin Yang, Dong Zhou, Ziyou Gao, Shlomo Havlin
摘要: 理解人类移动模式的重要性已导致许多研究检查其时空尺度规律。这些研究主要揭示了人类旅行可能是高度非均匀的,具有距离和时间的幂律比例分布。然而,到目前为止,还没有解决在飞行相同的空中距离时调查和量化时间和空间变化程度的问题。使用来自五个大城市的出租车数据,我们重点关注几种新的距离和时间度量,以探索出租车出行路线在高峰期和非高峰期相对于其典型路线的时空变化。为了使用单一度量比较所有旅行,我们计算了高峰期和非高峰期所有出发地 (OD) 的实际旅行距离与平均旅行距离之间以及实际旅行时间与平均旅行时间之间的比率分布。通过这种方式,我们测量了所有单个行程路径的分布相对于它们的平均行程路径的比例。我们的结果令人惊讶地证明了距离比和时间比的分布非常广泛,其特征是长尾幂律分布。此外,所有分析的城市在高峰时段的指数都比非高峰时段的指数大。我们认为,较短行程长度和时间的有趣结果(以高峰时段的较大指数为特征)是由于与非高峰时段相比,高峰时段旅客的可用性更高……
CasSeqGCN:结合网络结构和时间序列来预测信息级联原文标题: CasSeqGCN: Combining Network Structure and Temporal Sequence to Predict information Cascades
地址: http://arxiv.org/abs/2110.06836
作者: Yansong Wang, Xiaomeng Wang, Radosław Michalski, Yijun Ran, Tao Jia
摘要: 信息级联研究中的一项重要任务是根据信息过去的传播轨迹预测信息的未来接收者。虽然网络结构是传播的支柱,但如果不理解网络动态,就很难做出准确的预测。扩展序列中的时间信息刻画了许多隐藏特征,但仅基于序列的预测有其局限性。最近的努力开始探索将网络结构和时间特征结合起来进行更准确预测的可能性。尽管如此,将这两个相互依赖的因素有效和最佳地关联起来仍然是一个挑战。在这里,我们提出了一种新的端到端预测方法 CasSeqGCN,其中同时考虑了结构和时间特征。级联分为多个快照,记录网络拓扑和节点状态。图卷积网络(GCN)用于学习快照的表示。动态路由和长短期记忆(lstm)模型用于聚合节点表示和提取时间信息。与其他最先进的基线方法相比,CasSeqGCN 可以更准确地预测未来的级联大小。消融研究表明,改进主要来自输入和 GCN 层的设计。总之,我们的方法证实了在级联预测中结合结构和时间特征的好处,这不仅带来了新的见解,而且还可以作为未来研究的有用基线方法。
Ousiometrics and Telegnomics:意义的本质符合二维的强弱和危险安全框架,多样化的语料库呈现出安全偏差原文标题: Ousiometrics and Telegnomics: The essence of meaning conforms to a two-dimensional powerful-weak and dangerous-safe framework with diverse corpora presenting a safety bias
地址: http://arxiv.org/abs/2110.06847
作者: P. S. Dodds, T. Alshaabi, M. I. Fudolig, J. W. Zimmerman, J. Lovato, S. Beaulieu, J. R. Minot, M. V. Arnold, A. J. Reagan, C. M. Danforth
摘要: 我们将“ousiometrics”定义为对传达有意义信号的任何上下文中的基本意义的研究,而“telenomics”则定义为对遥感知识的研究。从 20 世纪中叶出现的工作开始,意义的本质已被普遍接受,因为它被评估、效力和激活 (EPA) 三个正交维度很好地刻画。通过重新检查英语的第一种类型,然后是标记,并通过使用自动注释的直方图——“ousiograms”——我们在这里发现: 1. 用罗盘来最好地描述单词所传达的含义的本质-like power-danger (PD) 框架,以及 2. 对大规模英语语料库的不同集合的分析——文学、新闻、维基百科、谈话电台和社交媒体——表明自然语言表现出系统性的偏见安全、低危险的词——重新诠释了 Pollyanna 原则对书面表达的积极偏见。为了帮助证明我们选择的维度名称的合理性,并帮助解决用双极形容词对表示观察到的 ousimetric 维度的问题,我们介绍和探索“同义词”和“反义词”——同义词和反义词的 ousimetric 对应物。我们进一步表明,PD 框架将情感的环模型修改为更一般的心理状态模型。最后,我们使用我们的发现来构建和测试原型“ousiometer”,这是一种测量时间语料库的 ousiometric 时间序列的电工工具。我们认为,我们的功率危险体表测量框架为基于熵的测量提供了补充,并且可能对研究跨生物和人工生命的各种通信有价值。
声明:Arxiv文章摘要版权归论文原作者所有,机器翻译后由本人进行校正整理,未经同意请勿随意转载。本系列在公众号“网络科学研究速递”(netsci)和个人博客进行同步更新。