Processing math: 90%
  • 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于随机块模型的社区隐藏统一框架

刘栋, 刘侠, 贾若雪, 张文生

刘栋, 刘侠, 贾若雪, 张文生. 基于随机块模型的社区隐藏统一框架[J]. 计算机研究与发展, 2024, 61(7): 1850-1862. DOI: 10.7544/issn1000-1239.202330533
引用本文: 刘栋, 刘侠, 贾若雪, 张文生. 基于随机块模型的社区隐藏统一框架[J]. 计算机研究与发展, 2024, 61(7): 1850-1862. DOI: 10.7544/issn1000-1239.202330533
Liu Dong, Liu Xia, Jia Ruoxue, Zhang Wensheng. A Unified Framework for Community Hiding Based on Stochastic Block Model[J]. Journal of Computer Research and Development, 2024, 61(7): 1850-1862. DOI: 10.7544/issn1000-1239.202330533
Citation: Liu Dong, Liu Xia, Jia Ruoxue, Zhang Wensheng. A Unified Framework for Community Hiding Based on Stochastic Block Model[J]. Journal of Computer Research and Development, 2024, 61(7): 1850-1862. DOI: 10.7544/issn1000-1239.202330533
刘栋, 刘侠, 贾若雪, 张文生. 基于随机块模型的社区隐藏统一框架[J]. 计算机研究与发展, 2024, 61(7): 1850-1862. CSTR: 32373.14.issn1000-1239.202330533
引用本文: 刘栋, 刘侠, 贾若雪, 张文生. 基于随机块模型的社区隐藏统一框架[J]. 计算机研究与发展, 2024, 61(7): 1850-1862. CSTR: 32373.14.issn1000-1239.202330533
Liu Dong, Liu Xia, Jia Ruoxue, Zhang Wensheng. A Unified Framework for Community Hiding Based on Stochastic Block Model[J]. Journal of Computer Research and Development, 2024, 61(7): 1850-1862. CSTR: 32373.14.issn1000-1239.202330533
Citation: Liu Dong, Liu Xia, Jia Ruoxue, Zhang Wensheng. A Unified Framework for Community Hiding Based on Stochastic Block Model[J]. Journal of Computer Research and Development, 2024, 61(7): 1850-1862. CSTR: 32373.14.issn1000-1239.202330533

基于随机块模型的社区隐藏统一框架

基金项目: 国家自然科学基金项目(62072160)
详细信息
    作者简介:

    刘栋: 1976年生. 博士,教授. 主要研究方向为复杂网络分析和教育数据挖掘

    刘侠: 1996年生. 硕士研究生. 主要研究方向为复杂网络分析

    贾若雪: 1998年生. 硕士研究生. 主要研究方向为复杂网络分析

    张文生: 1965年生. 博士,教授. 主要研究方向为人工智能、统计机器学习、大数据模式挖掘、医学数据分析与推理、计算机视觉

    通讯作者:

    张文生(wensheng.zhang@ia.ac.cn

  • 中图分类号: TP391

A Unified Framework for Community Hiding Based on Stochastic Block Model

Funds: This work was supported by the National Natural Science Foundation of China (62072160).
More Information
    Author Bio:

    Liu Dong: born in 1976. PhD, professor. His main research interests complex network analysis and educational data mining

    Liu Xia: born in 1996. Master candidate. Her main research interest includes complex network analysis

    Jia Ruoxue: born in 1998. Master candidate. Her main research interest includes complex network analysis

    Zhang Wensheng: born in 1965. PhD, professor. His main research interests include artificial intelligence, statistical machine learning, big data pattern mining, medical data analysis and reasoning, and computer vision

  • 摘要:

    社区检测是复杂网络分析的重要工具之一,可帮助深入了解网络的社区结构和节点间潜在的关系,但同时也带来了隐私泄露问题. 社区隐藏作为社区检测的伴生问题,旨在以最小的边扰动代价破坏网络的社区结构,近年来受到越来越多学者的关注. 但现有的社区隐藏方法忽略了网络的生成机制且缺少针对不同尺度隐藏的统一框架,因此提出了一种基于随机块模型的社区隐藏(community hiding-stochastic block model,HC-SBM)算法,该算法从网络生成机制角度构建了社区隐藏的统一框架,即实现微观(个体)、介观(社区)、宏观(网络)3个尺度上的社区检测算法攻击. 其基本思想是基于随机块模型刻画网络的生成机制,特别是网络社区形成和分裂的规律和模式,挖掘生成过程中的关键性链接以及链接集合,最终通过最小代价扰动策略破坏网络社区结构. 通过在真实网络上的大量实验,并与4种先进的基准算法进行比较,表明了提出的HC-SBM算法在社区隐藏效果更优.

    Abstract:

    As one of the important tools for complex network analysis, community detection can be used to help gain insight into the community structure of the network and the potential relationship between nodes. However, it also brings privacy leakage problems. As a concomitant problem of community detection, community hiding aims to destroy the community structure of the network with minimal edge disturbance cost, and it has received more and more attention from scholars in recent years. However, the existing community hiding methods ignore the network generation mechanism and lack a unified framework for hiding at different scales. Therefore, we propose a community hiding algorithm based on a stochastic block model (HC-SBM), which constructs a unified community hidden framework from the perspective of network generation mechanism, and launches three-scale attacks against community detection algorithm, namely, micro (individual), mesoscopic (community), and macro (network). The principle of this method is to illustrate the generation mechanism of the network based on the stochastic block model, especially the rules and patterns of the formation and division of the network community, mining critical links and link collections in the process of network generation.Finally, the network community structure is destroyed at the minimum cost of perturbation. Through extensive experiments on real networks and comparisons with several mainstream baseline algorithms, the proposed HC-SBM algorithm is shown to be superior in terms of community hiding effect.

  • 目前超级计算机已经迈入E级计算时代,但随着摩尔定律接近失效、颠覆性使能技术迟迟不能实现,超级计算机在访存、通信、能耗等方面仍面临严重的发展瓶颈[1]. 而MPI(message passing interface)集合通信[2]是高性能计算中最重要的通信类型,对整机系统的性能具有重要的影响,提升MPI集合通信性能是突破通信墙的重要手段. 传统的MPI集合通信是基于点到点消息实现的[3-4],随着系统规模的不断扩大,这种实现方式面临越来越严重的性能及可扩展性问题,而硬件集合通信具有性能高、可扩展性好等优点,正受到越来越多的关注[5].

    硬件集合通信中,数据沿聚合树进行规约或广播操作,聚合树的高度、负载均衡性等对集合操作的性能具有至关重要的影响. 本文研究了影响硬件集合通信性能的因素,提出了硬件集合通信开销模型,并以此为基础提出了构建硬件集合通信聚合树的方法. 本文主要贡献包括4个方面:

    1) 提出了硬件集合通信开销模型,能够较精确地计算硬件集合通信的时间开销;

    2) 研究了如何根据消息大小确定聚合树的宽度,从而在网络传输开销与数据计算开销之间取得平衡,以降低集合操作的延迟;

    3) 针对Ⅰ型聚合树,提出了最小高度分层k项聚合树构建方法,相比传统的Ⅰ型聚合树,降低了跨组聚合包的个数,减少了网络拥塞;

    4) 针对Ⅱ型聚合树,提出了最小代价Ⅱ型聚合树构建方法,减少了聚合树使用的交换机数量.

    近年来,网络计算技术发展迅速[6-7]. 网络计算可将数据规约计算、协议处理、数据加解密等原本由处理器承担的计算任务卸载到网络设备中进行,解放了CPU,使CPU可以专注于其他任务的处理. 在高性能计算领域,可利用网络计算提升MPI集合通信性能. 本文将基于网络计算实现的MPI集合通信称为硬件集合通信. MPI集合通信中,Barrier,Bcast,Reduce,Allreduce是应用最广泛的操作,它们均是1对多或多对1的通信模式,适于以硬件集合通信方式实现. 图1显示了Allreduce的实现过程,它利用聚合树完成数据聚合及结果分发操作,该树中叶节点对应通信进程,根节点及中间节点对应交换机. 进行集合通信时,数据先从叶节点向根节点聚合,并在聚合的过程中计算规约结果;到达根节点后再沿反方向将规约结果广播给所有叶节点. 其他集合操作的实现方式与此类似.

    图  1  基于网络计算的Allreduce操作实现过程
    Figure  1.  Implementation phases of Allreduce operation based on in-network-computing

    目前,很多公司推出了面向高性能计算的硬件集合通信技术,如IBM BlueG/Q中的硬件集合通信原语[8-11]、Mellanox的SHARP技术[5, 12-14]、神威互连网络中的硬件集合通信[15]等. 相较于点到点消息实现的集合通信,硬件集合通信的性能有了显著提升. Zimmer等人[16]在Summit系统中利用基准程序对SHARP性能进行了测试,4096个节点规模下集合消息性能至少提升了1倍.

    硬件集合通信除了需要特殊的硬件支持外,还需要网络管理软件的密切配合,以完成聚合树分配、多播路由配置等操作. 其中,聚合树分配是其中最为关键的操作. 现有的硬件集合通信技术在分配聚合树时还存在3个问题:

    1) 缺乏精确的集合通信开销模型,无法更好地指导聚合树构建. 基于α-β模型的软件集合通信开销模型[3]过于简化,而针对特定网络的专用模型又不具备通用性[17],它们均不适用于硬件集合通信.

    2) 构造聚合树时未考虑相互干扰问题. 当系统中存在大量通信域时,需要为每个通信域分配1棵独立的聚合树,以降低各通信域间的相互干扰,而现有的聚合树分配方法未充分考虑到该问题. 例如,SHARP技术中每个作业的所有通信域共享同一棵聚合树[18],这会产生严重的相互干扰. 现有的聚合树构建方法也没有考虑到同一聚合树内不同消息间的相互干扰问题. 例如,传统方法构建出的聚合树会产生较多的跨组通信,使得同一集合操作的不同消息因竞争通信链路而相互干扰.

    3) 未考虑硬件通信资源不够用问题. 网络中用于支持硬件集合通信的资源是有限的,而现有的聚合树构建方法未考虑该问题,导致出现通信资源不够用的情况. 例如,BlueG/Q中每个网络节点最多支持12棵聚合树,在很多情况下,由于聚合树数量不足,无法使用硬件集合通信[11].

    针对上述3个问题,本文研究如何建立硬件集合通信开销模型,以及如何基于该模型高效地构建聚合树.

    定义1. 互连网络. 互连网络定义为有向图I=(N, L),其中N为网络节点集合,L为通信链路集合. 网络节点包括网卡及交换机. 本文假设网卡在I中均是叶节点.

    定义2. 聚合树. 在互连网络I=(N, L)上目标集合MMN)对应的聚合树是一棵树A=(NA, LA),MNAN,其中M是通信域中各进程所在的网卡集合. A中边(μ,υ)的长度定义为Iμυ的距离,也即I中从μυ经过的网络链路数. A不必是I的子树,也即不要求LAL. 另外,M中允许有重复元素,从而使得每个节点上可同时运行多个通信进程. 聚合树还需满足度约束条件,也即每个节点的最大子节点数不能超过硬件阈值.

    定义3. 聚合树高度. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,A中从叶节点出发到达根节点所经过的边的最大条数,称为聚合树的高度. 只有1个节点的聚合树高度为0.

    定义4. 聚合树半径. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,A中从叶节点出发到根节点所经过边的长度之和的最大值称为聚合树半径. 聚合树半径实际上是从各叶节点出发沿该聚合树依次经过各祖先最终到达根节点时所经过的最大链路条数.

    现有的硬件集合通信技术中,有的仅支持将集合操作卸载到网卡中进行,有的则还可将集合操作卸载到交换机中进行. 根据不同的卸载位置,本文将聚合树分为Ⅰ型聚合树及Ⅱ型聚合树2种类型.

    定义5. Ⅰ型聚合树. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,若M = NA,则称A为Ⅰ型聚合树. 该类聚合树中,集合操作均被卸载到网卡中执行,且仅使用进程所在的那些网卡.

    定义6. Ⅱ型聚合树. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,T=(NT, LT)是I的一棵子树,MNANTN,且T中叶节点均在M中. 若uNAuA中的父亲p也是uT中的某个祖先,则称A为Ⅱ型聚合树. Ⅱ型聚合树中的集合操作均被卸载到交换机中进行.

    图2显示了Ⅰ型聚合树和Ⅱ型聚合树. 假设有8个进程参与集合通信,每个网卡上1个进程,互连网络的拓扑结构如图2(a)所示;图2(b)是一棵Ⅰ型聚合树,高度为3,半径为12;图2(c)是一棵Ⅱ型聚合树.

    图  2  Ⅰ型聚合树和Ⅱ型聚合树
    Figure  2.  Aggregate trees of type Ⅰ and type Ⅱ

    本文采用式(1)~(4)所示的开销模型,模型中各变量的含义如表1所示. 本文关注于如何降低聚合过程的开销,下面着重对聚合过程开销进行说明.

    表  1  硬件集合通信开销模型中使用的符号
    Table  1.  Symbols Used in the Cost Model of Hardware Supported Collectives
    符号 含义
    Tcoll 集合操作的总时间开销
    Tpost_wr 应用投递1个集合操作描述符的时间
    Tfetch_wr 网卡读取1个集合操作描述符的时间
    Tfetch_data 网卡从内存读取操作数的时间
    Taggregate 聚合过程的时间开销
    Tbcast 广播过程的时间开销
    Twrite_wc 网卡写完成条目及结果到内存的时间
    Tnoise 噪声导致的开销
    S 用户消息大小(不超过2 KB)
    S 聚合包大小
    S 规约数据长度
    β PCIE链路/网络链路带宽
    l 消息经过1条网络链路的时间
    hatree 聚合树高度
    ratree 聚合树半径
    P 进程总数
    k k叉树的宽度或k项树的基
    θ 每个聚合包的匹配处理时间
    γ 单位长度数据的规约计算时间
    δ 任2个进程间单播路由的最大跳步数
    下载: 导出CSV 
    | 显示表格

    Taggregate是聚合过程的时间,其包括聚合包在网络链路上的传输时间,以及在网络节点内的处理时间. 假设聚合树是k叉完全树,聚合树的半径为ratree,则聚合包在网络链路中的传输总时间为ratree×l. 设每个聚合包的匹配处理时间为θ、存储转发时间为Sβ、规约计算时间为S*×γ,则聚合包在网络节点内的处理总时间为hatree×k×(θ+Sβ+S*×γ). 最终得到式(2)所示的聚合时间开销.

    为进一步简化模型,除了假设聚合树是k叉完全树之外,还假设任意2个进程之间单播路由的路径长度相等,均需经过δ条链路,则对Ⅰ型聚合树,hatreelogkPratreeδ×logkP,从而得到式(3)所示的聚合过程开销. 而对Ⅱ型聚合树,hatreelogkPratree0.5δ,从而得到式(4)所示的聚合过程开销.

    Tcoll=Tpost\_wr+Tfetch\_wr+Tfetch\_data+Taggregate+Tbcast+Twrite\_wc+Tnoise, (1)
    Taggregate=ratree×l+hatree×k×(θ+Sβ+S*×γ), (2)
    Taggregate\_IlogkP×[δl+k(θ+Sβ+S*×γ)], (3)
    Taggregate\_II12δl+logkP×k(θ+Sβ+S*×γ). (4)

    本文在新一代神威超级计算机上测试了各类集合消息的延迟,并与开销模型计算出的结果进行对比. 实验环境如图3所示.

    图  3  测试环境使用的2层胖树
    Figure  3.  2-level fat tree used in the test environment

    使用1个超节点进行测试,超节点内共有256个节点,每个节点安装1块消息处理芯片,每块消息处理芯片有2个网络端口,故整个超节点内共有512个网络端口. 这512个网络端口通过一棵2层胖树进行互连. 该胖树共有48台交换机和其中32台叶交换机和16台骨干交换机. 每台交换机的端口数均为40,其中有些端口未被使用. 每台叶交换机有16个端口用于连接消息处理芯片的网络接口,16个端口用于连接骨干交换机.

    分别在不同进程数下测试了各种类型、各种长度集合消息的延迟. 测试方法为:每种类型及长度均测试5000次,每次测试进程均记录集合操作的时间开销,取耗时最长的那个进程的时间开销作为该次集合通信的时间开销,再取这5000个时间开销的中位值作为当前类型、当前长度下集合消息的延迟.

    限于篇幅,本文仅显示了Ⅰ型聚合树的部分测试结果. 不同进程数下,长度为8 B的广播操作的理论计算延迟与实际测试延迟如图4所示;进程数为512时不同长度Bcast消息的理论计算延迟与实际测试延迟如图5所示. 可以看出,Ⅰ型聚合树的理论计算延迟与实际测试延迟最多相差0.5 μs. 这表明本文提出的硬件集合通信开销模型能够较准确地拟合实测延迟.

    图  4  不同进程数下集合操作的实测延迟及理论计算延迟
    Figure  4.  Measured latency and estimated latency of collectives for different count of processes
    图  5  进程数为512时不同消息大小下集合消息的实测延迟及理论计算延迟
    Figure  5.  Measured latency and estimated latency of collectives for different message size when process count is 512

    给定任意P个进程,为它们构造一棵开销最小的Ⅰ型聚合树是非常困难的,因为不但要考虑聚合树宽度、聚合树半径等因素,还要考虑通信与通信重叠、通信与计算重叠、消息间相互干扰等因素的影响,故目前Ⅰ型聚合树均是通过启发式算法进行构造. 本节首先研究如何根据消息类型、消息长度等确定Ⅰ型聚合树的宽度k,然后研究如何快速构造一棵聚合树,使得跨组聚合包的个数尽可能地少,尽量降低消息间的相互干扰.

    聚合过程的时间开销包括聚合包的传输时间以及处理时间. 聚合树的宽度k对聚合过程的时间开销具有重要影响. 直观上看,如果k很小,则聚合树很高,相应地聚合包的传输开销就很大;如果k很大,则每个网卡需要处理的聚合包很多,相应地聚合包的处理开销就很大. 需要研究k对聚合时间开销的影响.

    先看如何选择k才能使式(3)计算出的聚合开销F(k)最小. 记δ×l=αθ+S'β+S×γ=b,定义如式(5)所示的F(k),其导数函数如式(6)所示.

    F(k)=logkP×[δ×l+k×(θ+Sβ+S*×γ)]=logkP×[a+kb], (5)
    F(k)=(lnP)[kb(lnk1)a]kln2k. (6)

    使F(k)取最小值的k记为k,此时的F(k)记为F. 根据式(5)(6),要使F(k)取最小值,需F(k)=0,也即k(lnk1)=ab,而函数f(k)=k(lnk1)是单调递增的. 对不同的集合操作类型及消息长度,ab取值不同,使F(k)取最小值的k也不同. 在本文的实验环境中,对同步、广播操作来说,k = 41时F(k)取最小值.

    很多情况下,选择其他k值时,Fk)与F差别不大. 以同步、广播操作为例,在本文的实验环境中,设P = 512,a = 1.12 μs,b = 0.01 μs,F(k)的曲线如图6所示,可以看出,当24k64时,F(k)相差不大,不超过0.1 μs. 对每种类型、每种长度的集合消息,都可以确定区间[kmin,kmax],使得k[kmin,kmax]时,|F(k)F|ε成立(ε是常数). 本文测试环境中使用的k表2所示(仅显示了部分结果). 可以发现,随着聚合包长度增大,kminkmax均逐渐下降. 对该现象的直观解释是:当聚合包长度较小时,聚合包在网络链路上的传输时间在总聚合时间中占比最大,此时应该采用较大的k,从而使得聚合包在网络链路上的传输尽量并行;而当聚合包长度较大时,聚合包在网卡内的处理时间在总聚合时间中占比最大,此时应采用较小的k,以使更多的网卡参与聚合包的处理.

    图  6  同步、广播操作的F(k)曲线
    Figure  6.  Curve of F(k) for Barrier and Bcast operation
    表  2  测试环境中使用的Ⅰ型聚合树宽度
    Table  2.  Type Ⅰ Aggregate Tree Breadth Used in the Test Environment
    消息类型聚合包长度/Bkminkmax推荐k
    Barrier/Bcast0326432
    Reduce/AllReduce32166332
    Reduce/AllReduce64155332
    Reduce/AllReduce128134016
    Reduce/AllReduce256102816
    Reduce/AllReduce51281916
    Reduce/AllReduce10246128
    Reduce/AllReduce2048588
    下载: 导出CSV 
    | 显示表格

    确定k值后就可以构建聚合树了. 式(3)假设任意2个进程间的单播路由经过的链路数相等,但实际情况要复杂得多. 使用相同的k值构造的2棵聚合树值半径ratree可能不同,导致聚合包的传输开销不同. 带度约束的最小半径聚合树问题是NP难的[19-21],尚未有高效的求解办法. 本文目标不是构造最优聚合树,而是快速构造出一棵满足度约束条件、半径尽可能小、冲突尽可能少的聚合树. 本节首先介绍2种传统的聚合树构建方法.

    定义7. k叉树. k叉树是一棵完全树,除最后一个中间节点外,根节点及其他中间节点都有k个子节点,故k叉树是平衡树,每个中间节点处理的聚合包个数相等.

    k叉树中,按广度优先遍历方式为进程编号,根进程编号为0. 若进程在通信域内的编号为my_rank,则其父节点编号为(my_rank−1)/k,第i个子节点编号为my_rank×k+i(i1).

    由于未考虑网络拓扑结构,在胖树网络[22-23]、蜻蜓网络[24]等具有分组结构的网络中,k叉树会产生大量的组间通信,导致网络拥塞. 16个进程构建聚合树,其网络拓扑如图7 (a)所示,4叉树如图7(b)所示. 粗线表示该聚合包需要经过最顶层的交换机,图7(b)中共有8个聚合包经过最顶层的交换机. 如果最顶层的交换机传输能力不足,则很容易在顶层交换机处形成拥塞. 而图7(c)是另一棵聚合树,其高度、半径均与图7(b)所示聚合树一样,但仅有2个经过顶层交换机的聚合包,因而具有更优的性能.

    图  7  k叉树易产生大量的组间通信
    Figure  7.  k-ary aggregate tree is prone to generate lots of inter-group communication

    定义8. k项树. k项树[25]是一组递归定义的树Tn,其中T0是1个单节点的树;而Tn是由kTn1连接起来构成的树,其中k−1棵Tn1的根节点直接连接到另外那棵Tn1的根节点上. k项树第i层的节点数是(k1)i×Cin,节点总数是kn,高度为n.

    图8分别显示了一棵2项树及一棵4项树. 2项树是特殊的k项树,在软件集合通信中已得到了广泛使用,例如在MPICH中短的Bcast、Reduce均是通过2项树实现的[3];而大于2的k项树目前使用得较少.

    图  8  k项树(k=2, 4)
    Figure  8.  k-nomial tree (k=2, 4)

    k叉树不同,k项树中不同深度的节点拥有不同数量的子节点,其中根节点的子节点数最多,为(k1)×logkP;而随着深度的增加,子节点数越来越少,故k项树是非平衡树.

    由于k叉树是平衡树,k叉树中上层节点要等待下层节点处理完毕之后才开始处理聚合包,故上层节点会存在空等待现象. 而k项树是非平衡树,位于不同层的节点可以并发处理聚合包,不存在空等待现象.

    k项树中,按深度优先遍历方式为进程编号. 进程编号用k进制表示为kn1k2,k1,k0,其中最低位共有i个0(0in),则第i个位置0即可得到其父节点编号,从最低的i位中任选一位置为1,2,,k1,则得到其子节点的编号最多有i×k1)个子节点.

    每个进程调用算法1所示的build_k_nomial_tree函数计算parent_rankchildren_cnt. 与k叉树一样,k项树也会产生很多跨组通信.

    算法1. build_k_nomial_tree.

    输入:本进程编号 my_rank,基数k,进程总数P

    输出:父节点parent_rank,子节点数children_cnt, 子节点列表children[].

    mask=1,children_cnt=0;

    ② while(mask<P

    ③  if(my_rank%(k×mask)) then

    ④   parent_rank=my_rank/(k×mask)× (k×mask)

    ⑤    break;

    ⑥  end if

    ⑦  mask=mask×k

    ⑧ end while

    mask=mask/k

    ⑩ while(mask>0) do

    ⑪  for (r=1;r<kr++)

    ⑫    child=my_rank+mask×r

    ⑬    if (child < P) then

    ⑭     children[children_cnt]=child

    ⑮     children_cnt+=1;

    ⑯    end if

    ⑰   end for

    ⑱   mask=mask/k

    ⑲ end while

    ⑳ 返回parent_rankchildren_cntchildren.

    传统的聚合树构建方法未考虑网络拓扑结构,容易产生较多的组间通信,从而造成网络拥塞. 为解决此问题,本文提出了分层k项树构建方法.

    分层思想是优化集合通信的一种重要策略[26-29],该策略利用了不同的层具有不同数据传输性能的特点,将同一层内的进程组织成组,使尽可能多的通信在组内完成,以降低层间通信、提升集合消息性能.

    在构建Ⅰ型聚合树时,利用分层思想也可以降低聚合过程的时间开销. Zhao等人[25]提出了一种简单方法:先将进程分为不同的组,并为每个组单独构建一棵k项树;然后将各组的首进程组成一个新的组,并创建一棵k项树,从而将所有组连接起来形成一棵更大的k项树. 进行聚合操作时,同一个组内的进程会先聚合到本组的首进程,首进程再聚合到更高层的首进程,从而大大减少组间通信. 但该方法产生的k项树可能具有较大的高度. 图9举了一个例子:通信域内共有14个进程,依图案分属4个不同的组. 当k = 2时,构建的聚合树如图9(a)所示,其高度为4. 实际上,可以使某个组的首进程连接到另一个组的非首进程下,从而使得聚合树更加平衡,以降低聚合树的高度. 图9(b)即是一棵更优的聚合树,其高度为3. 本文的目标是在最小化组间通信的同时使聚合树高度最低.

    图  9  具有分层结构的聚合树
    Figure  9.  Aggregate tree with hierarchical structure

    本文将具有相同通信特性的一组进程称为一个进程组. 例如,位于同一节点内的多个进程,以及位于同一交换机内的多个进程等,均可构成一个进程组. 进程组可以嵌套,从而使得一个进程组可包含多个子进程组,最终构成1个层次结构.

    进程组由如图10所示的数据结构定义. 每个进程组都对应一棵k项树,按深度优先方式为k项树内的节点编号. 进程被映射到k项树的某个节点上,树中有些节点可能无映射进程. 该数据结构中,cntk项树的节点数,它必须是k的幂;ranks_idk项树内各节点对应的进程号,nodes_id是各进程对应的k项树节点号;sub_groups定义了属于该进程组的子进程组,共有sub_grp_cnt个子进程组.

    图  10  进程组的数据结构
    Figure  10.  The data structure of the process group

    下面探讨最小高度分层k项Ⅰ型聚合树问题. 给定m个互不相交的进程组g0,g1,,gm1g是满足2个条件的进程组:1)g包含g0,g1,,gm1的所有进程;2)g对应的k项树中,除首进程外其余进程的父节点均位于gi内;3)g对应的k项树中,每个节点的儿子数不超过硬件限制. 该问题为从中找出具有最小高度的进程组g,从而为进程组g0,g1,,gm1构建一棵高度最小的分层k项Ⅰ型聚合树. 进程组gi(0i<m)内嵌套的子进程组也需满足条件2.

    g0i是进程组gi首进程的进程号,根据k项树的性质,条件2等价于g.nodes[g0i]%(gi.cnt)=0且对gi内每个进程gjig.nodes[gji]/(gi.cnt)=g.nodes[g0i]/(gi.cnt),也即进程g0i被映射到某个编号为gi.cnt倍数的聚合树节点内,其余进程依次映射到后续节点内.

    给定m个进程组g0,g1,,gm1,且每个gi均已构建好各自的k项树之后,即完成了ranks的设置,采用算法2为这些进程组构建一棵更大的k项聚合树. 算法2采用贪心策略,每次找出2个最大的进程组g0g1,然后在g0的空闲子树内寻找能够容纳g1的位置. 如果找不到这样的位置,则将g0的聚合树高度加1,即cnt变为原来的k倍,从而使g0内有足够的空余位置容纳g1. 该过程持续下去,直到最终只剩1个进程组为止. 算法2行⑤代码用于为g[i]寻找可用的位置,仅需检查分块的第1个位置是否可用即可判断整个分块是否可用. 行⑫~⑭代码用于将g[i]ranks映射表拷贝到新的聚合树中.

    算法2. merge_groups.

    输入:子进程组列表g[]及列表长度m,基数k,父 进程组parent

    输出:无.

    ① 将g[0],g[1],,g[m1]按照cnt字段由大到 小的顺序排列;

    parent.cnt=g[0].cnt

    ③ for(i=0;i<m;++i

    ④  for(j=0;j<parent.cntj+=g[i].cnt

    ⑤   if(parent.ranks[j]==1)then

    ⑥    break;

    ⑦   end if

    ⑧  end for

    ⑨  if(jparent.cnt) then

    ⑩   parent.cnt=pareng×k

    ⑪  end if

    ⑫  for(x=0;x<g[i].cnt;++x

    ⑬   parent.ranks[j+x]g[i].ranks[x]

    ⑭  end for

    ⑮ end for

    采用数学归纳法可证明算法2所产生的k项树是高度最小的分层k项Ⅰ型聚合树,限于篇幅,不再赘述证明过程.

    算法3以递归方式为每个层次建立进程到聚合树节点的映射关系. 算法4根据拓扑信息建立分层的k项树. build_hierarchical_tree建立的聚合树中,每个组的进程均位于同一子树内,从而保证除该组的首进程外其余进程均向本组内的进程发送聚合包,故跨组聚合包的个数相比传统聚合树构建方法减少了. 在使用算法4时,需要选择合适的k,以保证聚合树内每个节点的儿子数不超过硬件限制.

    算法3. build_rank_mapping.

    输入:进程组g

    输出:无.

    ① if(g.sub_grp_cnt==0

    ②  return;

    ③ end if

    ④ for(i=0;i<g.sub_grp_cnt;++i

    ⑤  build_rank_mapping.sub_groups[i]);

    ⑥ end for

    merge_groupsg.sub_groups, g.sub_grp_cnt, k, g).

    算法4. build_hierarchical_tree.

    输入:本进程编号my_rank,基数k,进程总数P

    输出:父节点parent_rank,子节点数children_cnt.

    ① 根据网络拓扑信息构建进程组信息,其中 底层的组其sub_grp_cnt = 0,ranks填充为该 组内各进程的rank号,其他层的组需填充 sub_groups,最高层的组记为g

    build_rank_mappingg)

    ③ 遍历g.ranks找到my_rank在该数组内的下标 node_id

    ④调用build_k_nomial_treenode_id, k, g.cnt)获得 parent_node_id、子节点列表children及列 表长度cnt

    parent_rank=g.ranks[parent_node_id]

    children_cnt=0;

    ⑦ for (i=0;i<cnti++)

    ⑧  if (g.ranks[children[i]]1) then

    ⑨   children_cnt+=1;

    ⑩  end if

    ⑪ end for

    ⑫ 返回parent_rankchildren_cnt.

    本节研究构造Ⅱ型聚合树的方法. 构造Ⅱ型聚合树时需要综合考虑网络拓扑、进程位置等因素. 另外,在每个交换机内,每棵Ⅱ型聚合树都占用1个聚合树条目,而硬件支持的聚合树条目是有限的,故创建Ⅱ型聚合树时,还需要考虑是否有可用的聚合树条目.

    构造Ⅱ型聚合树时要考虑3个目标:1)最小化聚合树的半径,以降低集合操作延迟;2)尽量让不同的聚合树分布到不同链路上,以降低聚合树间的相互干扰;3)使用尽可能少的聚合树条目,以支持创建更多的Ⅱ型聚合树.

    本文分2个步骤构造Ⅱ型聚合树. 1)选择1个交换机作为树根,并构造1棵生成树(称为物理树);2)对物理树进行裁剪,去掉不需要的交换机.

    定义9. 物理树. 设M是某通信域内进程所在的网卡集合,T=(NT, LT)是互连网络I=(N, L)的一棵子树,若T满足2个条件,则称T是关于M的物理树:

    1)MNT

    2)T的叶节点除M中网卡之外,不包含任何其他网卡及交换机.

    定义10. 由物理树推导出的Ⅱ型聚合树. 设K是交换机节点的度约束函数,给定互连网络I=(N, L)上一棵关于M的物理树T=(NT, LT),由物理树T导出的Ⅱ型聚合树是满足2个条件的树A=(NA, LA):

    1)MNANT

    2)若uNAuA中的父亲p也是uT中的某个祖先;

    3)A中每个交换机sw的子节点数不大于度约束Ksw),其中Ksw)大于swT中的子节点数.

    实际上,由物理树T导出的Ⅱ型聚合树A可看成是将T中某些节点提升位置而得到的(仅能提升为其祖先的儿子).

    定义11. Ⅱ型聚合树的代价. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵Ⅱ型聚合树,A中交换机的个数称为该Ⅱ型聚合树的代价,记为costA).

    树根的位置决定了聚合树的半径,应该选择到通信域内各进程最大跳步数最小的交换机作为树根.

    本文采用集中式方法构建物理树. 在该方法中,由集中式的网络管理软件选择树根并构建物理树. 网络管理软件维护了网络的状态信息,包括交换机内空闲的聚合树条目数、网络链路的负载情况等. 网络管理软件可根据这些信息选择一个交换机作为树根.

    该方法具体过程为:先计算出每个交换机到通信域组内各进程的最小跳步数,据此找到所有的备选树根. 然后根据备选树根的负载情况对备选树根进行排序,优先使用负载低的树根. 选择好一个树根后,就可以构造一棵物理树,使得每个进程到树根的跳步数最少. 然后检查该物理树的每个交换机是否有空闲的聚合树条目可用. 若每个交换机都有空闲的聚合树条目,则返回该物理树;若失败,则尝试下一个树根.

    由物理树导出的最小代价Ⅱ型聚合树问题. 给定互连网络I=(N, L)上一棵关于M的物理树T=(NT, LT)及度约束函数K,在由物理树T导出的Ⅱ型聚合树中求代价最小的聚合树A.

    本文利用算法5所示的函数创建最小代价Ⅱ型聚合树. 可以证明算法5产生的聚合树A是由物理树T导出的最小代价Ⅱ型聚合树. 限于篇幅,证明不再赘述.

    算法5. build_minimum_type_Ⅱ_tree.

    输入:物理树T=(NT, LT),度约束函数K

    输出:聚合树A=(NA, LA).

    ①记T的根节点为r,若r不是交换机,则返回仅 包含节点r的聚合树;

    ②否则,对r的每个子节点si,记以si为根的子 树为Ti,调用build_minimum_type_Ⅱ_treeTi,K)产生由物理树Ti导出的最小代价Ⅱ 型聚合树Ai

    ③若r仅有1个子节点T1,则返回该子节点对应 的最小代价Ⅱ型聚合树A1

    ④否则,构造一棵树A=(NA, LA),r为根节点,各 Ai为子树;

    ⑤若Ar的子节点数小于r的度约束K(r),则

    ⑥  从所有Ai中找到一个最小的叶交换机L(叶 交换机是指所有子节点均是网卡的交换 机,最小是指子节点数最小);

    ⑦  从L中任选一进程p,使p成为r的儿子;

    ⑧  若L删掉p后仅剩1个儿子q,则将q设为 q祖父的儿子并删掉L

    ⑨  重复过程⑥~⑧,直到r的子节点数等于 K(r)为止;

    ⑩返回A.

    图11(a)显示了一棵物理树,该树中共有16个进程,使用了13个交换机,每个交换机的度约束均为5;其导出的最小代价Ⅱ型聚合树如图11(b)所示,仅使用了4个交换机.

    图  11  一棵物理树及其导出的最小代价Ⅱ型聚合树
    Figure  11.  A physical tree and its reduced minimum cost type Ⅱ aggregate tree

    在性能方面,Ⅰ型聚合树与Ⅱ型聚合树各有优势. 对长度较小的集合操作,聚合包的传输时间占主导,而Ⅱ型聚合树中聚合包传输路径较短,故延迟比Ⅰ型聚合树低. 对长度较大的集合操作,规约计算时间占主导,Ⅰ型聚合树可以将规约计算分布到大量网卡中并发进行,故延迟较小. 创建通信域时,需要综合考虑各方面因素,选择使用Ⅰ型聚合树还是Ⅱ型聚合树.

    为简化分析,假设Ⅱ型聚合树是标准的d叉树,记δ×l=αθ+Sβ+S×γ=b,则Ⅰ型、Ⅱ型聚合树的时间开销分别如式(7)(8)所示. 为简化讨论,仅考虑S=S=S的情况.

    Taggregate\_I(a+kb)logkP, (7)
    Taggregate\_IIa2+dblogdP. (8)

    定义如式(9)所示的函数F(d,k,P,S)

    F(d,k,P,S)=Taggregate\_ITaggregate\_II=(logkP0.5)a+(klogkPdlogdP)b, (9)
    FP=1P(a+kblnkdblnd), (10)
     FS=(1β+γ)(klogkPdlogdP). (11)

    可以根据式(9)~(11)分析F(d,k,P,S)的变化趋势,并据此构造一张静态映射表. 给定集合操作类型及消息长度后,通过查表即可快速确定聚合树类型及宽度. 表3列出了本文实验环境中如何根据聚合包长度来选择使用Ⅰ型聚合树还是Ⅱ型聚合树. 当申请不到创建Ⅱ型聚合树所需的通信资源时,需要回退到Ⅰ型聚合树.

    表  3  聚合树选择方法
    Table  3.  Method to Select Aggregate Tree
    d 聚合包长度/B 聚合树类型 k
    16 (0, 2 048] Ⅱ 型 16
    64 [0, 323] Ⅱ 型 64
    (323, 512] Ⅰ 型 16
    (512, 2 048] Ⅰ 型 8
    不能创建Ⅱ
    型聚合树时
    [0, 64] Ⅰ 型 32
    (64, 512] Ⅰ 型 16
    (512, 2 048] Ⅰ 型 8
    下载: 导出CSV 
    | 显示表格

    本节将在新一代神威超级计算机中对聚合树性能进行测试.

    首先测试不同的Ⅰ型聚合树集合消息的延迟. 对同步、广播、8B长度的规约操作而言,选择k = 32可以获得更好的性能,故分别构造了32叉树、32项树、分层32项树. 使用1个超节点进行测试,每个节点运行2个进程,每个进程使用1个网络端口,这2个端口间的通信不需要经过网络链路. 分别在2种场景下进行测试.

    在2层标准胖树中进行测试. 分层32项树使用了3个层次,首先将位于同一节点的2个进程组成1个组,这2个进程间的通信不需要经过网络链路;然后将位于同一交换机内的16个进程组成1个组,该组内的进程通信时仅需经过2条链路;最后将位于同一超节点内的所有进程组成1个组,该组内的进程通信时需经过4条链路.

    图12显示了Bcast-8B,Bcast-2KB这2种集合操作的测试结果. 可以看出:1)大部分情况下32叉树、32项树几乎具有相同的延迟;2)大部分情况下,分层32项树的延迟低32叉树、32项树约0.6 μs. 分层32项树延迟低的原因是:它先把位于同一节点内的2个进程组成1个组,而这2个进程间通信不需要经过网络链路,故延迟较低. 需要指出的是,进程数较少时分层32项树的延迟反而高于另外2种聚合树,原因是此时的分层32项树的高度大于32叉树、32项树;随着进程数的增多,这3种聚合树将具有相同的树高.

    图  12  标准胖树拓扑中不同进程数下3种聚合树的消息延迟
    Figure  12.  Messages latency of three types of aggregate trees for different count of processes in standard fat-tree topology

    不同消息长度时3种构造方法下的聚合树的性能如图13所示. 测试时使用了512个进程,每个进程使用1个网络端口. 测试结果与图12的测试结果一致,即32叉树和32项树的性能相当,而分层32项树的延迟明显低于32叉树和32项树.

    图  13  标准胖树拓扑中不同消息长度下3种聚合树的消息延迟
    Figure  13.  Messages latency of three types of aggregate trees for different message sizes in standard fat-tree topology

    使用如图14所示的裁剪胖树进行测试. 该拓扑中,同一交换机内的不同网络端口向其他交换机内的网络端口发消息时会共享一条通信链路. 测试时还在网络中加入了网络噪声,该噪声消耗约80%的网络带宽.

    图  14  测试使用的2层裁剪胖树示意图
    Figure  14.  Illustration of two-layer pruned fat-tree used in the test

    分别测试不同进程数时3种方法构建的聚合树的性能,并将之与标准胖树下的测试结果进行了对比,结果如图15所示. 可以看出,加入网络噪声后,3种构建方法的集合消息延迟相比标准胖树下有显著增大. 其中32叉树增幅最大,分层32项树增幅最小.

    图  15  裁剪胖树拓扑下有干扰时集合通信消息延迟
    Figure  15.  Collective messages latency in pruned fat-tree topology with inference

    图16显示了进程数为512时,3种方法构建的聚合树中跨组聚合包的数量,其中每条实线上的数字表示该实线所连接的2个交换机间的聚合包个数. 在32叉树中,大量聚合包发送到1号交换机的不同进程内,故每个集合操作中,0号交换机与1号交换机间链路上需传输496个聚合包,从而产生严重的链路竞争.

    图  16  裁剪胖树下3种聚合树构建方法的跨组聚合包
    Figure  16.  Inter-group aggregation packets of three types of aggregate trees constructed methods in pruned fat-tree

    表4显示了不同进程数时3种聚合树下Bcast-8 B 的延迟对比,可以看出,在存在噪声干扰的情况下,分层32项树的延迟相比传统的聚合树构建方法下降了24%~89%. 这表明,相比另外2种聚合树构建方法,分层32项树具有更少的跨组聚合包,因而存在带宽竞争的情况下可以显著降低集合消息的延迟.

    表  4  裁剪胖树拓扑下有干扰时不同进程数下Bcast-8B延迟
    Table  4.  Bcast-8B Latency for Different Count of Processes in Pruned Fat-tree Topology with Inference
    进程数 32叉树下
    延迟/μs
    32项树下
    延迟/μs
    分层32项树
    下延迟/μs
    64 19.92(↓39%) 17.79(↓32%) 12.11
    128 25.11(↓49%) 18.58(↓31%) 12.75
    192 35.75(↓64%) 18.54(↓31%) 12.73
    256 42.87(↓70%) 18.62(↓32%) 12.75
    320 71.81(↓82%) 18.86(↓32%) 12.83
    384 97.33(↓86%) 18.94(↓30%) 13.33
    448 115.82(↓87%) 18.80(↓26%) 13.94
    512 136.60(↓89%) 19.48(↓24%) 14.89
    注:括号内的百分比表示分层32项树相比32叉树、32项树的延迟下降比例;↓表示分层32项树相比32叉树、32项树的延迟下降比例.
    下载: 导出CSV 
    | 显示表格

    需要注意的是,随着进程数的增大,32项树的延迟增加较缓慢,而分层32项树的延迟增加略快(分层32项树相比32项树的延迟下降比例由进程数为64时的32%下降为进程数为512时的24%). 这是因为,在裁剪胖树中,随着进程数的增大,32项树中每条链路上传输的最大聚合包数保持为16,故32项树的延迟变化不大;而分层32项树中每条链路上传输的最大聚合包数由1逐渐增大到31,故分层32项树的延迟会缓慢增加. 但可以肯定的是,随着进程数的进一步增大,分层32项树的延迟仍低于32项树,这是因为32项树中每2个相邻交换机间都需要传输16个聚合包,从而更易受网络噪声的干扰.

    除此之外,本文还在其他场景下测试了3种聚合树构建算法的消息延迟. 例如,利用更多超节点进行了测试,其网络拓扑采用3层裁剪胖树,故分层32项树可采用更多的层次. 此实验的测试结论与上述测试结论一致,即分层32项树延迟最低,32项树次之,32叉树延迟最高. 限于篇幅,不再赘述其详细测试数据.

    本节对Ⅰ型聚合树及Ⅱ型聚合树的性能进行对比. 测试环境如图17所示. 其中Ⅰ型聚合树采用64叉树进行构建,Ⅱ型聚合树的树根建在最高层的那个交换机上. 分别测试了不同进程数下2种类型聚合树的性能,Bcast-8 B及Bcast-2 KB的延迟如图18所示. 可以看出,Ⅱ型聚合树的延迟比Ⅰ型聚合树低1 μs左右.

    图  17  使用网络拓扑对比Ⅰ型聚合树及Ⅱ型聚合树性能
    Figure  17.  Network topology used to compare the performance of type Ⅰ and type Ⅱ aggregate trees
    图  18  Ⅰ型聚合树及Ⅱ型聚合树的性能对比
    Figure  18.  Performance comparison of type Ⅰ and type Ⅱ aggregate trees

    本节测试最小代价Ⅱ型聚合树构造算法的有效性以及不同通信模式下聚合树条目的使用情况.

    MPI集合通信中,一般将进程划分为2维或3维网格通信域,其每个维度中的每行或每列都是一个通信域. 本文测试了5种典型的通信模式,包括2种2维网格结构、2种3维网格结构,以及1种随机模式. 选择的2维网格结构中,256×160通信模式按拓扑结构划分通信域,模拟拓扑感知的通信模式,即第1维有160个通信域,故每个通信域都位于同一个超节点内;而202×202通信模式存在很多跨超节点的通信域,模拟拓扑无感的通信模式. 2种3维网格结构也是按类似原则进行划分的. 随机模式是指进程随机加入一个通信域.

    下面从2个方面证明最小代价Ⅱ型聚合树构造算法的有效性:一方面,最小代价Ⅱ型聚合树占用的聚合树条目数相比传统方法构建的Ⅱ型聚合树有显著下降;另一方面,最小代价Ⅱ型聚合树构建算法创建聚合树时的失败率相比传统的Ⅱ型聚合树也有显著下降.

    1) 聚合树占用的总条目数

    首先测试每种通信模式下聚合树占用的总条目数. 假设每个交换机内的聚合树条目数足够多. 对于每种通信模式,依次为每个通信域构建Ⅱ型聚合树,并统计占用的聚合树条目总数,结果如图19所示. 其中,传统方法构建的Ⅱ型聚合树是指利用集中式方法构建的物理树. 可以看出,所有通信模式下,最小代价Ⅱ型聚合树占用的条目总数明显低于传统方法构建的聚合树所占用的条目数,最少下降了90%. 这表明最小代价Ⅱ型聚合树算法在降低聚合条目使用量方面具有显著效果. 有些通信模式下,最小代价Ⅱ型聚合树的聚合树条目总数等于通信域个数,这是因为在这些通信模式下,每个通信域的最小代价Ⅱ型聚合树都仅使用1个交换机.

    图  19  不同通信模式下Ⅱ型聚合树使用的总聚合树条目数
    Figure  19.  Total count of aggregate tree entries used by type Ⅱ aggregate trees for different kinds of communication patterns

    2)创建聚合树时的失败率

    将每个交换机的聚合树条目数设为16,然后在每种通信模式下依次为每个通信域构建Ⅱ型聚合树,并记录创建失败的次数. 定义创建聚合树时的失败率为:=,结果如图20所示. 可以看出,最小代价Ⅱ型聚合树算法均能为每个通信域成功构建聚合树;而传统的Ⅱ型聚合树构建方法失败率很高,最高可达74.51%.

    图  20  不同通信模式下创建Ⅱ型聚合树的失败率
    Figure  20.  Failure rate of creating type Ⅱ aggregate trees in different communication patterns

    需要指出的是,将交换机的聚合树条目数设为更小的值后,某些通信模式下也存在不能创建最小代价Ⅱ型聚合树的情况,但其失败率仍低于传统的Ⅱ型聚合树构建方法,结果不再赘述.

    综上所述,最小代价Ⅱ型聚合树算法可以显著减少对交换机内聚合树条目资源的占用,从而可以支持创建更多的Ⅱ型聚合树.

    硬件集合通信中,聚合树对集合操作的性能具有重要影响. 构建聚合树时,需要综合考虑聚合树半径、宽度、负载均衡、网络噪声等的影响. 本文提出了硬件集合通信开销模型,并据此提出了3种构建聚合树的方法,包括:1)根据聚合包大小确定Ⅰ型聚合树的宽度;2)最小高度分层Ⅰ型聚合树构建方法;3)最小代价Ⅱ型聚合树构建方法. 然后在神威互连网络中对聚合树构建方法进行了全面测试,在存在网络噪声的情况下,分层Ⅰ型聚合树的消息延迟相比传统构建方法下降了24%~89%;最小代价Ⅱ型聚合树使用的交换机聚合条目数相比传统构建方法下降了约90%.

    下一步,我们将利用真实的应用程序对聚合树构建方法的性能进行更全面的测试. 另外,我们还将研究如何利用硬件集合通信提升长度较大的规约、广播等集合操作的性能,扩大硬件集合通信的适用范围.

    作者贡献声明:陈淑平提出研究思路,设计算法、实验,分析实验数据并撰写论文;尉红梅指导算法及完善实验方案;王飞、李祎负责算法实现、测试数据的整理与分析;何王全、漆锋滨提出研究课题,把握论文创新性,并对论文进行修改.

  • 图  1   HC-SBM示意图

    Figure  1.   Illustration of HC-SBM

    图  2   Blogs 下HC-SBM与对比算法度量指标Hμ比较

    Figure  2.   Comparison of the metric H, μ between HC-SBM and the comparative algorithms under Blogs

    表  1   HC-SBM与主流社区隐藏算法的对比

    Table  1   Comparison Between HC-SBM and the Mainstream Community Hiding Algorithms

    算法 操作 隐藏尺度 是否考虑生成机制
    ROAM 加边和减边 微观
    DICE 加边或减边 介观
    SBA[7] 加边或减边 介观
    RAT[5] 加边和减边 宏观
    HC-SBM(本文) 加边和减边 微观、介观和宏观
    下载: 导出CSV

    表  2   符号表示

    Table  2   Symbolic Representation

    符号 描述
    G/G 原网络/扰动网络
    Gi 网络G的一个子图
    C/C 原网络社区划分/扰动网络社区划分
    Ci/Ci 任意一个原网络社区/任意一个扰动网络社区
    AD 社区检测算法
    β 扰动预算
    E+/E 添加链接/删除链接
    Ct 目标社区
    vt 目标节点
    {\boldsymbol{P}} 重连概率矩阵
    下载: 导出CSV

    表  3   实验数据集

    Table  3   Experimental Datasets

    数据集 节点数 边数 各社区检测算法下的社区数 数据集描述
    Multilevel Fast_greedy Label_propagation Leiden
    Blogs 1222 16714 11 11 3 11 超链接博客网络
    Power 4941 6594 40 41 481 490 美国电网
    Hep 8361 15751 1376 1411 1 858 1375 高能理论科学家合作网络
    Astro 16706 121251 1072 1168 1550 1078 天体物理学合作作者网络
    下载: 导出CSV

    表  4   HC-SBM与宏观社区隐藏基线算法性能对比

    Table  4   Performance Comparison Between HC-SBM and Macro Community Hiding Baseline Algorithms

    数据集 度量 指标 对比算法 Multilevel Fast_greedy Label_propagation Leiden
    1% 3% 5% 1% 3% 5% 1% 3% 5% 1% 3% 5%
    Blogs NMI HC-SBM 0.724 0.594 0.438 0.814 0.567 0.421 0.806 0.671 0.567 0.836 0.568 0.473
    Pro-SBM 0.841 0.621 0.480 0.822 0.595 0.481 0.827 0.596 0.534 0.792 0.639 0.489
    RAT 0.897 0.737 0.727 0.839 0.772 0.764 0.894 0.842 0.802 0.862 0.698 0.680
    ARI HC-SBM 0.841 0.734 0.456 0.897 0.716 0.571 0.882 0.768 0.681 0.901 0.556 0.488
    Pro-SBM 0.912 0.765 0.615 0.907 0.743 0.632 0.895 0.704 0.642 0.892 0.785 0.662
    RAT 0.950 0.861 0.859 0.922 0.880 0.873 0.946 0.909 0.887 0.932 0.838 0.824
    Jaccard HC-SBM 0.841 0.734 0.491 0.893 0.720 0.594 0.889 0.793 0.726 0.895 0.558 0.508
    Pro-SBM 0.907 0.760 0.620 0.903 0.741 0.642 0.900 0.744 0.699 0.889 0.780 0.662
    RAT 0.946 0.854 0.852 0.917 0.875 0.868 0.948 0.913 0.893 0.927 0.831 0.824
    Power NMI HC-SBM 0.841 0.804 0.769 0.883 0.800 0.754 0.893 0.884 0.873 0.887 0.824 0.786
    Pro-SBM 0.886 0.814 0.771 0.883 0.838 0.798 0.896 0.887 0.876 0.894 0.845 0.816
    RAT 0.852 0.819 0.801 0.890 0.839 0.811 0.901 0.889 0.889 0.900 0.866 0.857
    ARI HC-SBM 0.646 0.615 0.575 0.748 0.594 0.536 0.493 0.471 0.435 0.781 0.659 0.596
    Pro-SBM 0.731 0.638 0.579 0.762 0.705 0.638 0.523 0.491 0.469 0.770 0.691 0.647
    RAT 0.693 0.632 0.592 0.770 0.700 0.649 0.540 0.506 0.503 0.801 0.732 0.713
    Jaccard HC-SBM 0.488 0.456 0.415 0.608 0.436 0.380 0.329 0.309 0.280 0.649 0.502 0.435
    Pro-SBM 0.586 0.480 0.419 0.625 0.556 0.480 0.356 0.326 0.308 0.635 0.538 0.489
    RAT 0.541 0.473 0.432 0.636 0.550 0.493 0.371 0.340 0.337 0.676 0.587 0.563
    Hep NMI HC-SBM 0.854 0.819 0.794 0.923 0.839 0.801 0.920 0.933 0.892 0.878 0.824 0.802
    Pro-SBM 0.875 0.861 0.814 0.929 0.846 0.815 0.947 0.942 0.929 0.891 0.861 0.837
    RAT 0.896 0.868 0.842 0.944 0.863 0.838 0.945 0.942 0.938 0.888 0.877 0.857
    ARI HC-SBM 0.514 0.493 0.422 0.820 0.617 0.582 0.621 0.601 0.569 0.561 0.535 0.501
    Pro-SBM 0.520 0.562 0.439 0.824 0.618 0.580 0.644 0.676 0.422 0.596 0.552 0.537
    RAT 0.598 0.567 0.472 0.848 0.627 0.559 0.616 0.597 0.633 0.564 0.601 0.512
    Jaccard HC-SBM 0.351 0.346 0.277 0.710 0.591 0.403 0.469 0.428 0.377 0.429 0.380 0.339
    Pro-SBM 0.358 0.397 0.289 0.719 0.562 0.424 0.476 0.512 0.269 0.432 0.388 0.374
    RAT 0.433 0.402 0.316 0.744 0.617 0.427 0.497 0.437 0.466 0.499 0.436 0.351
    Astro NMI HC-SBM 0.671 0.643 0.587 0.631 0.520 0.479 0.874 0.780 0.654 0.710 0.676 0.615
    Pro-SBM 0.710 0.652 0.603 0.626 0.561 0.503 0.890 0.811 0.688 0.725 0.688 0.668
    RAT 0.688 0.647 0.657 0.726 0.606 0.600 0.910 0.851 0.847 0.742 0.692 0.696
    ARI HC-SBM 0.362 0.340 0.319 0.353 0.306 0.261 0.800 0.669 0.489 0.411 0.429 0.403
    Pro-SBM 0.396 0.373 0.321 0.344 0.318 0.273 0.801 0.683 0.503 0.420 0.445 0.430
    RAT 0.348 0.363 0.372 0.577 0.364 0.334 0.848 0.735 0.738 0.472 0.451 0.444
    Jaccard HC-SBM 0.255 0.239 0.202 0.303 0.250 0.208 0.731 0.643 0.493 0.315 0.270 0.265
    Pro-SBM 0.262 0.244 0.206 0.270 0.254 0.211 0.749 0.644 0.512 0.381 0.302 0.290
    RAT 0.277 0.247 0.246 0.460 0.284 0.263 0.802 0.689 0.690 0.394 0.374 0.300
    注:1%,3%,5%为扰动预算占网络总链接数的百分比;加粗部分为最小值,值越小宏观社区隐藏效果越好.
    下载: 导出CSV

    表  5   HC-SBM与介观社区隐藏基线算法性能对比

    Table  5   Performance Comparison Between HC-SBM and Mesoscopic Community Hiding Baseline Algorithms

    数据集 对比算法 Multilevel Fast_greedy Label_propagation Leiden
    H μ H μ H μ H μ
    Blogs HC-SBM 0.515 0.491 0.381 0.497 0.500 0.497 0.305 0.487
    DICE 0.395 0.489 0.334 0.495 0.350 0.492 0.272 0.486
    SBA 0.345 0.449 0.336 0.167 0.449 0.495 0.281 0.484
    Power HC-SBM 0.485 0.776 0.445 0.581 0.332 0.640 0.454 0.563
    DICE 0.264 0.183 0.354 0.180 0.402 0.460 0.430 0.553
    SBA 0.480 0.684 0.425 0.569 0.318 0.770 0.439 0.562
    Hep HC-SBM 0.357 0.426 0.385 0.149 0.443 0.140 0.421 0.536
    DICE 0.326 0.235 0.350 0.087 0.189 0.056 0.340 0.465
    SBA 0.102 0.143 0.362 0.053 0.312 0.076 0.400 0.378
    Astro HC-SBM 0.402 0.431 0.440 0.647 0.491 0.341 0.413 0.754
    DICE 0.340 0.401 0.455 0.524 0.375 0.253 0.327 0.731
    SBA 0.272 0.327 0.330 0.221 0.372 0.258 0.240 0.154
    注:加粗部分为最大值,值越大介观社区隐藏效果越好.
    下载: 导出CSV

    表  6   HC-SBM与微观社区隐藏基线算法性能对比

    Table  6   Performance Comparison Between HC-SBM and Micro-Community Hiding Baseline Algorithms

    数据集 对比算法 Multilevel Fast_greedy Label_propagation Leiden
    Blogs HC-SBM 1 3 2 1
    Dr 3 6 6 1
    Power HC-SBM 2 1 1 2
    Dr 3 2 3 2
    Hep HC-SBM 1 2 2 1
    Dr 3 3 3 2
    Astro HC-SBM 3 4 3 3
    Dr 4 5 4 3
    注:加粗部分为最小值,值越小微观社区隐藏效果越好.
    下载: 导出CSV
  • [1]

    Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47−97 doi: 10.1103/RevModPhys.74.47

    [2]

    Newman M E. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167−256 doi: 10.1137/S003614450342480

    [3]

    Zhou Yang, Cheng Hong, Yu Xu. Graph clustering based on structural/attribute similarities[J]. ACM Transactions on Accessible Computing, 2009, 2(1): 718−729

    [4]

    Oukemeni S, Rifà-Pous H, Puig J M. Privacy analysis on microblogging online social networks: A survey[J]. ACM Computing Surveys, 2019, 52(3): 1−36

    [5]

    Nagaraja S. The impact of unlinkability on adversarial community detection: Effects and countermeasures[C]// Proc of the 10th Int Symp on Privacy Enhancing Technologies. Berlin: Springer, 2010: 253−272

    [6]

    Waniek M, Michalak T P, Rahwan T, et al. Hiding individuals and communities in a social network[J]. Nature Human Behaviour, 2018, 2(2): 139−147 doi: 10.1038/s41562-017-0290-3

    [7]

    Fionda V, Pirrò G. Community deception or: How to stop fearing community detection algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(4): 660−673 doi: 10.1109/TKDE.2017.2776133

    [8]

    Chen Jinyin, Chen Lihong, Chen Yixian, et al. GA-based Q-attack on community detection[J]. IEEE Transactions on Computational Social Systems, 2019, 6(3): 491−503 doi: 10.1109/TCSS.2019.2912801

    [9]

    Liu Dong, Chang Zhengchao, Yang Guoliang, et al. Hiding ourselves from community detection through genetic algorithms[J]. Information Sciences, 2022, 614: 123−137 doi: 10.1016/j.ins.2022.10.027

    [10]

    Holland P W, Laskey K B, Leinhardt S. Stochastic block models: First steps[J]. Social Networks, 1983, 5(2): 109−137 doi: 10.1016/0378-8733(83)90021-7

    [11] 陶海成,卜湛,曹杰. 基于多目标强化学习的社区隐藏框架[J]. 中国科学:信息科学,2021,51(7):1131−1145 doi: 10.1360/SSI-2020-0229

    Tao Haicheng, Bu Zhan, Cao Jie. Community hidden framework based on multi-objective reinforcement learning[J]. SCIENTIA SINICA Informationis, 2021, 51(7): 1131−1145 (in Chinese) doi: 10.1360/SSI-2020-0229

    [12]

    Newman M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577−8582 doi: 10.1073/pnas.0601602103

    [13]

    Girvan M, Newman M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821−7826 doi: 10.1073/pnas.122653799

    [14]

    Yang Liang, Cao Xiaochun, He Dongxiao, et al. Modularity based community detection with deep learning[C]//Proc of the 25th Int Joint Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2016: 2252−2258

    [15]

    Bisma S K, Muaz A N. Network community detection: A review and visual survey[J]. arXiv preprint, arXiv: 1708.00977, 2017

    [16]

    Barnes E R. An algorithm for partitioning the nodes of a graph[J]. SIAM Journal on Algebraic Discrete Methods, 1982, 3(4): 541−550 doi: 10.1137/0603056

    [17]

    Yang Gui, Zheng Wenping, Che Chenhao, et al. Graph-based label propagation algorithm for community detection[J]. International Journal of Machine Learning and Cybernetics, 2020, 11(6): 1319−1329 doi: 10.1007/s13042-019-01042-0

    [18]

    Fan Lilin, Song Kaiyuan, Liu Dong. A noise reduction method for semi-supervised community detection based on harmonic function[J/OL]. International Journal of Modern Physics B, 2018, 32(14) [2023-09-11].https://www.x-mol.com/paper/1308287826419486720?adv

    [19]

    Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structures of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814−818 doi: 10.1038/nature03607

    [20]

    Jaswant M, Devi V S. Overlapping community detection in social network using disjoint community detection[C]//Proc of the 8th Symp Series on Computational Intelligence. Piscataway, NJ: IEEE, 2015: 764−771

    [21]

    Li Jia, Zhang Honglei, Han Zhichao, et al. Adversarial attack on community detection by hiding individuals[C] //Proc of the 29th Int World Wide Web Conf. New York: ACM, 2020: 917−927

    [22]

    Chen Xianyu, Jiang Zhongyuan, Li Hui, et al. Community hiding by link perturbation in social networks[J]. IEEE Transactions on Computational Social Systems, 2021, 8(3): 704−715 doi: 10.1109/TCSS.2021.3054115

    [23]

    Liu Yiwei, Liu Jiamou, Zhang Zijian, et al. Rem: From structural entropy to community structure deception[C] // Proc of the 33rd Conf on Neural Information Processing System. Cambridge, MA: MIT, 2019: 12938−12948

    [24]

    Liu Dong, Yang Guoliang, Wang Yanwei, et al. How to protect ourselves from overlapping community detection in social networks[J]. IEEE Transactions on Big Data, 2022, 8(4): 894−904 doi: 10.1109/TBDATA.2022.3152431

    [25]

    Yang Guoliang, Wang Yanwei, Chang Zhengchao, et al. Overlapping community hiding method based on multi-level neighborhood information[J]. Symmetry, 2022, 14(11): 23−28

    [26] 刘学艳. 面向复杂网络分析的随机块模型研究[D]. 长春:吉林大学,2021

    Liu Xueyan. Research on stochastic block models for complex network analysis [D]. Changchun: Jilin University, 2021(in Chinese)

    [27]

    Lada A, Natalie S. The political blogosphere and the 2004 U. S. election: Divided they blog[C]//Proc of the 11th ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2005: 36−43

    [28]

    Haiko L W, Duncan J. Collective dynamics of small world networks[J]. Nature, 1998, 393(6684): 440−442 doi: 10.1038/30918

    [29]

    Newman M E. The structure of scientific collaboration networks[J]. Proceedings of the National Academy of Sciences, 2001, 98(2): 404−409 doi: 10.1073/pnas.98.2.404

    [30]

    Razieh H, Alireza R. AntLP: Ant-based label propagation algorithm for community detection in social networks[J]. CAAI Transactions on Intelligence Technology, 2020, 5(1): 34−41 doi: 10.1049/trit.2019.0040

    [31]

    Traag A V, Waltman L, Eck V J. From Louvain to Leiden: Guaranteeing well-connected communities[J]. arXiv preprint, arXiv: 1810.08473, 2019

    [32]

    Vincenet D B, Jean-Loup G, Renaud L, et al. Fast unfolding of communities in large networks[J/OL], Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10)[2023-09-11].https://www.x-mol.com/paper/1415733752522543104?adv

    [33]

    Liu Xuecheng, Fu Luoyi, Wang Xinbing, et al. ProHiCo: A probabilistic framework to hide communities in large networks[C] //Proc of the 40th IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2021: 1−10

    [34]

    Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9): 219−228

  • 期刊类型引用(1)

    1. LUO Haoran,HU Shuisong,WANG Wenyong,TANG Yuke,ZHOU Junwei. Research on Multi-Core Processor Analysis for WCET Estimation. ZTE Communications. 2024(01): 87-94 . 必应学术

    其他类型引用(4)

图(2)  /  表(6)
计量
  • 文章访问数:  101
  • HTML全文浏览量:  25
  • PDF下载量:  40
  • 被引次数: 5
出版历程
  • 收稿日期:  2023-06-20
  • 修回日期:  2023-10-08
  • 网络出版日期:  2024-04-23
  • 刊出日期:  2024-07-03

目录

/

返回文章
返回