时态多层网络中的社区检测及其应用

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Community detection in temporal multilayer networks, with an application
  to correlation networks》
---
作者：
Marya Bazzi, Mason A. Porter, Stacy Williams, Mark McDonald, Daniel J.
  Fenn, and Sam D. Howison
---
最新提交年份：
2017
---
英文摘要：
  Networks are a convenient way to represent complex systems of interacting entities. Many networks contain \"communities\" of nodes that are more densely connected to each other than to nodes in the rest of the network. In this paper, we investigate the detection of communities in temporal networks represented as multilayer networks. As a focal example, we study time-dependent financial-asset correlation networks. We first argue that the use of the \"modularity\" quality function---which is defined by comparing edge weights in an observed network to expected edge weights in a \"null network\"---is application-dependent. We differentiate between \"null networks\" and \"null models\" in our discussion of modularity maximization, and we highlight that the same null network can correspond to different null models. We then investigate a multilayer modularity-maximization problem to identify communities in temporal networks. Our multilayer analysis only depends on the form of the maximization problem and not on the specific quality function that one chooses. We introduce a diagnostic to measure \\emph{persistence} of community structure in a multilayer network partition. We prove several results that describe how the multilayer maximization problem measures a trade-off between static community structure within layers and larger values of persistence across layers. We also discuss some computational issues that the popular \"Louvain\" heuristic faces with temporal multilayer networks and suggest ways to mitigate them.
---
中文摘要：
网络是一种表示相互作用实体的复杂系统的便捷方式。许多网络包含节点的“社区”，这些节点之间的连接比其他网络中的节点更紧密。在本文中，我们研究了在表示为多层网络的时态网络中的社区检测。作为一个重点例子，我们研究了时间相关的金融资产关联网络。首先，我们认为“模块化”质量函数的使用取决于应用程序，该函数是通过比较观察到的网络中的边缘权重与“空网络”中的预期边缘权重来定义的。在模块化最大化的讨论中，我们区分了“零网络”和“零模型”，并强调同一个零网络可以对应不同的零模型。然后，我们研究了一个多层模块化最大化问题，以确定时态网络中的社区。我们的多层分析只取决于最大化问题的形式，而不取决于所选择的具体质量函数。我们将{emph}的多层网络划分引入到诊断}。我们证明了几个结果，这些结果描述了多层最大化问题如何衡量层内静态社区结构和层间更大持久性值之间的权衡。我们还讨论了流行的“Louvain”启发式算法在时间多层网络中面临的一些计算问题，并提出了缓解这些问题的方法。
---
分类信息：

一级分类：Physics        物理学
二级分类：Physics and Society        物理学与社会
分类描述：Structure, dynamics and collective behavior of societies and groups (human or otherwise). Quantitative analysis of social networks and other complex networks. Physics and engineering of infrastructure and systems of broad societal impact (e.g., energy grids, transportation networks).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--
一级分类：Computer Science        计算机科学
二级分类：Social and Information Networks        社会和信息网络
分类描述：Covers the design, analysis, and modeling of social and information networks, including their applications for on-line information access, communication, and interaction, and their roles as datasets in the exploration of questions in these and other domains, including connections to the social and biological sciences. Analysis and modeling of such networks includes topics in ACM Subject classes F.2, G.2, G.3, H.2, and I.2; applications in computing include topics in H.3, H.4, and H.5; and applications at the interface of computing and other disciplines include topics in J.1--J.7. Papers on computer communication systems and network protocols (e.g. TCP/IP) are generally a closer fit to the Networking and Internet Architecture (cs.NI) category.
涵盖社会和信息网络的设计、分析和建模，包括它们在联机信息访问、通信和交互方面的应用，以及它们作为数据集在这些领域和其他领域的问题探索中的作用，包括与社会和生物科学的联系。这类网络的分析和建模包括ACM学科类F.2、G.2、G.3、H.2和I.2的主题；计算应用包括H.3、H.4和H.5中的主题；计算和其他学科接口的应用程序包括J.1-J.7中的主题。关于计算机通信系统和网络协议（例如TCP/IP）的论文通常更适合网络和因特网体系结构（CS.NI）类别。
--
一级分类：Physics        物理学
二级分类：Adaptation and Self-Organizing Systems        自适应和自组织系统
分类描述：Adaptation, self-organizing systems, statistical physics, fluctuating systems, stochastic processes, interacting particle systems, machine learning
自适应，自组织系统，统计物理，波动系统，随机过程，相互作用粒子系统，机器学习
--
一级分类：Quantitative Finance        数量金融学
二级分类：Statistical Finance        统计金融
分类描述：Statistical, econometric and econophysics analyses with applications to financial markets and economic data
统计、计量经济学和经济物理学分析及其在金融市场和经济数据中的应用
--

---
PDF下载：
--> Community_detection_in_temporal_multilayer_networks,_with_an_application_to_corr.pdf (1.12 MB)

2022-5-7 07:16:35 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：maximization Applications Quantitative Econophysics Architecture

时间多层网络中的群体检测及其在相关网络中的应用*玛丽娅·巴齐+、梅森·A·波特、斯泰西·威廉姆斯§、马克·麦克唐纳§、丹尼尔·J·芬§、山姆·D·豪森¨摘要。网络是一种表示相互作用实体的复杂系统的便捷方式。许多网络包含节点的“社区”，这些节点之间的连接比网络其余部分中的节点更紧密。在本文中，我们研究了以多层网络表示的时间网络中的社区检测。作为一个重点例子，我们研究了与时间相关的金融资产关联网络。我们首先认为，“模块化”质量函数的使用取决于应用，该函数是通过比较观察到的网络中的边缘权重与“零网络”中的预期边缘权重定义的。在模块化最大化的讨论中，我们区分了“零网络”和“零模型”，并强调了相同的零网络可以对应不同的零模型。然后，我们研究了一个多层模块化最大化问题，以确定时态网络中的社区。我们的多层分析只取决于最大化问题的形式，而不取决于选择的特定质量函数。我们引入了一种诊断方法来度量多层网络分区中社区结构的持久性。我们证明了几个结果，这些结果描述了多层最大化问题如何衡量层内静态社区结构和跨层持久性更大值之间的权衡。我们还讨论了时态多层网络中流行的“Louvain”启发式算法面临的一些计算问题，并提出了缓解这些问题的方法。关键词。社区结构、多层网络、时态网络、模块化最大化、财务关联网络。AMS科目分类。62H30、91C20、94C15、90C351。介绍

在最简单的形式中，网络只是一个图：它由一组表示实体的节点和一组表示这些实体之间交互的成对节点之间的边组成。我们可以考虑加权图（其中每条边都有一个相关的边权重，可以量化利益的相互作用）或未加权图（带二元边权重的加权图）。网络为跨多个学科的复杂系统提供了有用的表示[54]。常见的类型包括社交网络（通过网络和/或在线互动产生）、信息网络（如万维网网页之间的超链接）、基础设施网络（如城市之间的交通路线）和生物网络（如细胞或蛋白质之间的代谢互动、食物网等）。给定一个系统的网络表示，应用粗粒化技术来研究介于“微尺度”（例如节点和成对交互）和“宏观尺度”（例如总边缘）之间的特征是有用的*这项工作得到了欧洲委员会资助的EPSRC（BK/10/41）、HSBCBank和FET前瞻性项目PLEXMATH（FP7-ICT-2011-8；317614）颁发的案例学生奖的支持。+牛津工业和应用数学中心，数学研究所，牛津OX26GG，英国(bazzi@maths.ox.ac.uk)——牛津工业和应用数学中心，数学研究所，牛津2 6GG，英国；以及英国牛津大学牛津分校卡布丁复杂性中心(porterm@maths.ox.ac.uk)§全球研究，汇丰银行，伦敦E14 5HQ，英国。英国牛津OX26GG数学研究所牛津工业和应用数学中心；以及英国牛津大学牛津曼定量金融研究所(howison@maths.ox.ac.uk).重量和度数分布[55,61]。

因此，我们研究“中尺度”特征，如核心-外围结构和（特别是）群落结构。不严格地说，网络中的社区（或集群）是一组相互“更紧密”连接的节点，而不是网络其余部分的节点[25,61]。当然，准确定义“密集连接”对于社区检测来说是必要的。从一开始就必须认识到，这一定义是主观的，尤其可能取决于相关应用。相应地，可能需要定制社区检测方法。我们将自己限制为硬分区，其中每个节点都被分配给一个社区，我们使用术语“分区”来表示“硬分区”。考虑“软分区”也很重要，但这超出了本文的范围，因为社区可以重叠[25,37,58,61]。社区结构分析在广泛的应用中非常有用；[25,27,55,61]中描述了其中许多。在社交网络中，社区可以揭示具有共同兴趣、居住地或其他相似性的人群[56,73]。在生物系统中，群落可以揭示负责合成或调节重要化学产品的官能团[32,45]。在本文中，我们以金融资产关联网络为例[8,15]。尽管市场、金融产品和地理位置多种多样，但金融资产在资产类别内部和类别之间都可能表现出强烈的时间相关性。市场从业者（例如，投资组合多元化）主要关心的是估计这些相关性的强度，并确定高度相关的资产集[48,74]。大多数检测社区的方法都是为静态网络设计的。

然而，在许多应用程序中，实体和/或实体之间的交互会在一段时间内演化。在此类应用中，可以使用时态网络的形式，其中节点和/或其边缘权重随时间变化[34,35]。这对许多应用程序都很重要，包括人与人之间的交流[75]、一对多信息传播（如Twitter网络[29]和Facebook网络[77]）、细胞生物学[35]、神经科学[7]、生态学[35]、金融[22–24,57]等等。在依赖时间的网络中，有两种主要的方法被用来检测社区。第一种方法是通过将不同时间点的演化网络快照聚合为单个网络来构建静态网络（例如，通过在所有时间点上获取每条边的平均或总边权重，如果节点集随时间变化，这可能会有问题，这也会对实体之间的交互动力学做出限制性假设[33]）。然后可以使用标准的网络技术。

第二种方法需要在不同时间对网络时序序列的每个元素使用静态社区检测技术，或在不同时间间隔（可以重叠或不重叠）上对网络聚合时序序列（如上计算）的每个元素使用静态社区检测技术，然后跟踪序列中的社区[3、22、23、36、47、58]。第三种方法是在一个更大的网络中嵌入一个按时间顺序排列的网络序列[19,60]（相关的想法也可以在其他上下文中找到[49,70]）。节点的“度”是连接到它的边的数量；度是未加权网络的“强度”（2.1）的特例。我们需要区分这种聚合和移动窗口上一组时间序列的平均值，以构建相关矩阵，然后将其解释为时间演化网络的固定时间快照。尽管这两种情况都涉及在一个时间窗口上进行平均，但前者需要对网络进行平均，而后者需要对时间序列集合（每个节点一个）进行平均，而没有直接可观测的边权重。序列的每个元素都是一个网络层，不同时间点的节点由层间边缘连接。这种方法在[49]中介绍，结果网络是一种多层网络[11,39]。该方法与前一种方法的主要区别在于，非零层间边缘的存在导致了一层中确定的社区与其他层中的连接模式之间的依赖性。到目前为止，大多数使用时间网络多层表示的计算都假设层间连接是“对角的”（即，它们只存在于同一节点的副本之间）和“顺序的”（即，它们只存在于连续层之间）[39]。

对角线是节点身份在时间上持久性的自然模型，而序数保持时间顺序。[49]的作者将静态网络的普遍聚类方法模块化最大化推广到多层网络。模块化是一种功能，通过计算观察到的网络中集合中的总边缘权重与从某个“零模型”生成的“零网络”中相同集合中的总预期边缘权重之间的差异，来衡量将网络划分为不相交的节点集的“质量”[25，61]。模块化最大化包括在网络分区空间上最大化模块化质量函数。（在实践中，考虑到这个最大化问题的组合复杂性，我们使用一些计算启发式，并找到一个局部最大值[30]。）直观地说，空模型控制人们预期在网络中发现的连接模式，并使用模块化最大化来识别观察到的网络中比预期更强的连接模式。在本文中，我们讨论了两个主要问题：（1）空网络的选择和（2）层间边缘在多层模块化最大化中的作用。我们在第4节讨论第一个问题，在第5节讨论第二个问题。第4节和第5节中的大部分结论适用于任意选择的单层网络，我们使用财务相关网络作为示例。在第2节和第3节中，我们概述了现有的结果。我们对单层网络第2节中的模块化函数给出了精确的定义，其中（重要的）我们在模块化最大化中区分了“空网络”和“空模型”。在第4节中，我们将讨论给定应用程序的空网络选择。

在第3节中，我们描述了[49]中提出的单层网络的推广。到目前为止，几乎没有任何理论解释了零层间耦合（即在每一层上独立实现单层模块化最大化）获得的多层分区与非零层间耦合获得的多层分区的区别。在第5节中，我们证明了多层最大化问题最优解的几个理论性质，以便更好地理解这种划分如何不同，以及人们如何在实践中利用这种差异。我们还描述了使用流行的Louvain启发式[10]解决多层最大化问题时出现的两个计算问题，并提出了缓解这些问题的方法。第5节的结果取决于最大化问题的形式，如果使用模块化质量函数以外的质量函数，则仍然适用，前提是它具有相同的形式（例如，它对“稳定性”有效[18,42]）。我们在第6.2节中得出结论。单层模块化最大化。2.1. 模块化函数。考虑一个N节点网络G，让节点对之间的边缘权重为{Aij | i，j∈ {1，…，N}，所以A=（Aij）∈RN×n是G的邻接矩阵。在本文中，我们只考虑对称邻接矩阵（以及无向网络），所以对于所有i和j，Aij=ajif。节点i的强度iski=NXj=1Aij=NXj=1Aji，（2.1），由a的i行（或列）和给出。在研究网络结构时，比较观察到的和预期的是有用的。我们将空模型定义为邻接矩阵集上的概率分布，将空网络定义为特定空模型下的预期邻接矩阵。

从松散的意义上讲，空模型扮演着先验模型的角色，因为它们控制着人们预期在被调查系统中发现的特征。因此，我们可以考虑已知（或可疑）的连接模式，这些模式可能会掩盖我们希望通过社区检测等过程发现的未知连接模式。例如，在社交网络中，人们通常将空网络中节点的强度作为其观察到的强度HKI[53,55,61]。我们将在第4节讨论金融资产相关网络中使用该空网络。在代表不同位置之间疾病或信息传播的空间网络中，一些作者使用了零网络，其中两个位置之间的边缘权重与它们之间的距离成反比[21,66]。正如我们在第1节中所讨论的，我们使用模块化最大化将网络划分为一组称为“社区”的节点，这些节点的总内部边缘权重大于由某个空模型生成的空网络中相同集合的预期总内部边缘权重[25、55、56、61]。模块化最大化包括找到最大化这种差异的分区[25,61]。（正如我们前面提到的，在实践中，我们使用一些计算启发式，并找到一个局部最大值[30]）。在本文中，对于模块化质量函数，我们不局限于通常选择的空网络（即第2.4.1小节中的“纽曼-吉尔文”空网络），我们忽略了依赖于空网络选择的任何规范化常数，但不影响给定空网络的模块化最大化问题的解决方案。因此，模块化充当了一个“质量函数”Q:C→ R、 其中，集合C是所有可能的N节点网络分区的集合。假设我们把一个网络的C划分成K个不相交的节点集{C，…，CK}。

然后我们可以定义一个从节点集{1，…，N}到整数集{1，…，K}的映射c（·），使得c（i）=c（j）=K当且仅当Ck中的节点i和jlie。我们使用术语“全局最大值”来指代模块化最大化问题的解决方案，使用术语“局部最大值”来指代通过计算启发式获得的解决方案。我们称c（i）为c分区中节点i的集合赋值（或当c是全局或局部最大值时的communityassignment）。给定分区c的模块化值为Q（c | a；P）：=NXi，j=1（Aij）- Pij）δ（ci，cj），（2.2），其中P=（Pij）∈ RN×Nis是零网络的邻接矩阵，ci是c（i）的简写符号，δ（ci，cj）是Kronecker-delta函数。我们将模极大化问题陈述如下：∈CNXi，j=1（Aij- Pij）δ（ci，cj），（2.3），也可以写成maxC∈CQ（C | B）或maxC∈CPNi，jBijδ（ci，cj），其中B=A- P是所谓的模块化矩阵[53]。在优化问题（2.3）中，分区中的集合数K是自由的。（换句话说，在所有N节点分区的集合上最大化。）当我们考虑一个特定的分区C时，我们只考虑K的固定值∈ C、 当| C |=K时，我们允许在第4节和第5节的财务数据的所有数值实验中使用自边。（特别是，A是Aii=1的皮尔逊相关矩阵。）在本文的其余部分中，我们假设集合C中的每个部分都包含集合，这些集合在邻接矩阵B的图中没有多个连通分量。从（2.3）中可以清楚地看出，只有当两个节点被分配到同一集合时，对模块性的成对贡献才会被计算。当观察到的节点i和j之间的边缘权重aijb大于（分别小于）它们之间的预期边缘权重pijb时，这些贡献为正（分别为负）。