基于节点相似度与影响力的CCN社区划分方案_张建伟.pdf

第 22卷 第 2期2023年 2月Vol.22 No.2Feb.2023软 件 导 刊Software Guide基于节点相似度与影响力的CCN社区划分方案张建伟1，崔梦梦1，蔡增玉2（1.郑州轻工业大学 软件学院；2.郑州轻工业大学 计算机与通信工程学院，河南 郑州 450002）摘要：内容中心网络（CCN）的内容检索过程存在低效冗余问题，为提升其性能，提出一种基于节点相似度和影响力的CCN社区划分方案（SI-LPA）。首先提出基于特征向量中心性和改进标签传播算法的社区划分方案，以帮助内容检索；随后利用节点与邻居节点间相似性和影响力提出一种更新标签值的方法；最后在每一个划分好的社区上选择竞争力最大的节点部署SDN控制器，以帮助实现更好的管理社区功能以及进行社区间路由。实验表明，引入SDN控制器和社区划分可以加快内容检索和路由分发的速度，从而提高CCN路由的性能。关键词：内容中心网络；社区划分；节点相似度；节点影响力；软件定义网络DOI：10.11907/rjdk.221303开 放 科 学（资 源 服 务）标 识 码（OSID）：中图分类号：TP393.02 文献标识码：A文章编号：1672-7800（2023）002-0095-05CCN Community Partition Method Based on Node Similarity and InfluenceZHANG Jian-wei1，CUI Meng-meng1，CAI Zeng-yu2（1.School of Software，Zhengzhou University of Light Industry；2.School of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450002，China）Abstract：The content retrieval process of content center network（CCN）is inefficient and redundant，In order to improve the performance of CCN，proposes a CCN community partition scheme（SI-LPA）based on node similarity and influence.Firstly，a community partition scheme based on feature vector centrality and improved label propagation algorithm is proposed to help content retrieval.Then，using the similarity and influence between nodes and neighbor nodes，a method to update the tag value is proposed；Finally，select the most competitive node on each divided community to deploy SDN controller to help better manage community functions and route between communities.Experiments show that the introduction of SDN controller and community partition can accelerate the speed of content retrieval and routing distribution，so as to improve the performance of CCN routing.Key Words：CCN；community division；node similarity；node influence；SDN0 引言传统基于TCP/IP的网络架构不能很好地满足日益增加的网络流量需求1-4，用户在请求内容时，往往不知道内容提供者，从而造成无法将目的地址嵌入到兴趣包中进行转发的问题。以内容为中心的网络（Content Centric Network，CCN）从提供商驱动的端到端通信模式转换到了兴趣驱动的内容检索通信模式，这使得 CCN 不能像 TCP/IP那样根据源、目的IP地址采用逐跳返回的方法进行路由，因此，怎样设计更高效的 CCN 路由方案是 CCN 网络架构亟需解决的一个问题。近年来，CCN路由机制得到了广泛的研究5-7，为解决CCN的可扩展性和大规模部署问题，有两个较为有效的方案：一是与 SDN的结合8-10，因为 SDN作为未来互联网的一种独特的模型，实现了控制平面与数据平面相分离；另一个方案是进行社区划分11-14，但在进行社区划分时社区的大小和内容很难确定，给社区划分带来了新的挑战。现有若干社区发现算法，如Girvan等15的基于边介数的分裂GN算法，每次删除边介数最大的边，直到所有的边都被移除；Blondel等16提出模块度最大化的louvain算法，将每个点看作独立社区，计算社区折叠后社区间和社区内收稿日期：2022-03-19基金项目：国家自然科学基金项目（62072416）；河南省科技攻关项目（202102210176）作者简介：张建伟（1971-），男，博士，CCF会员，郑州轻工业大学软件学院教授、硕士生导师，研究方向为新一代网络、大数据安全；崔梦梦（2016-），女，郑州轻工业大学软件学院硕士研究生，研究方向为新一代网络；蔡增玉（1979-），男，硕士，CCF会员，郑州轻工业大学计算机与通信工程学院副教授、硕士生导师，研究方向为机器学习、人工智能。2023 年软 件 导 刊的连边权重，直到最后合为一个社区；Raghavan等17提出标签传播算法（LPA），相比前两种算法，该算法具有线性的时间复杂度，适合用于大型网络中的社区划分。LPA 算法的核心思想为：给途中每个节点分配标签值，以代表节点所在的社区。找出邻居节点中标签传播值最大的节点（最大值不唯一时，随机选择一个），将该节点加入该社区，并更新节点的标签传播值，当节点标签传播值不再变化时，停止迭代；否则重复上述步骤。在传统LPA算法中，初始标签值的确定具有随机性，这使划分好的社区存在稳定性差和准确性低的缺点，为解决该问题，很多学者提出了改进措施。Luo等18通过优化目标函数来提升社区划分的质量，但LPA的稳定性较差；张猛等19通过计算标签重要性，改变标签更新序列，但未考虑节点之间的相似性；Song等20通过计算节点相似性，改变标签更新序列，但未考虑节点的重要性。目前，LPA算法在社区划分实际应用中仍存在不足之处，为进一步提高社区划分的稳定性和准确性，本文提出一种基于节点兴趣相似度和社交影响力的CCN社区划分方法（SI-LPA），综合考虑节点相似性和重要性对于社区的影响，并引入特征向量中心性优化初始社区结构，使其划分的社区更具有代表性与稳定性。1 SI-LPA算法1.1兴趣相似度兴趣权重表示节点对一个兴趣字段的历史请求次数，用Wik表示节点vi对兴趣字段fk的兴趣权重，当vi生成一个包含fk的请求时：Wki=Wki+1（1）节点的兴趣相似度为两个节点的兴趣集合中相同兴趣字段的兴趣权重集合对应的Tanimoto系数相关性。假设节点vi与vj相同的兴趣字段个数为p，则节点vi与vj的兴趣相似度为：Twij=1 k pWkiWkj1 k p()Wki2+1 k p()Wkj2-1 k pWkiWkj（2）1.2节点社交影响力节点之间的社交距离与通过这两点时间的数据流量成正比，与两节点间距离成反比，且与节点的度有关。Swij=dij()1+|()i ()jmin()ki，kjdis()i，j（3）ki=|(i)|，kj=|(j)|（4）其中，dij为流经节点vi与vj数据流量的总和，（i）与（j）分别为节点vi与vj邻居节点的集合，ki与kj分别为节点vi与vj的度，dis（i，j）为节点vi与vj之间的欧氏距离。1.3特征向量中心性用 A=（eij）nn表示无向图对应的邻接矩阵，X=（x1，x2，xn）表示该矩阵的一个特征向量。对于任意路由节点vi，其对应的特征向量值为xi，为邻接矩阵A的特征向量X对应的特征值，则：xi=11 j neijxj，(1 i n)（5）利用上述公式，当对特征向量值进行多次迭代，其值达到稳态时，此时的 xi为节点 vi对应的特征向量中心性。为方便计算，在区间（0，1）内对特征向量中心性进行标准化，用xi表示标准化后特征向量中心性的值，则：xi=xi1 j nxj2，(1 i n)（6）1.4标签传播值对 n个特征向量中心性的值降序排列，选择其中前 k个值对应的节点作为初始社区，用C1，C2，Ck表示，对k个社区以并行方式基于层次便利的方法发展其它节点作为其社区成员。其中标签传播值的更新规则如下：Li=argmaxj Nilajkjwij（7）wij=Twij+(1-)Swij（8）其中，Ni为节点vi的邻居节点的集合，laj为邻居节点vj的标签活性值，kj为邻居节点vj的度，wij为节点vi与节点vj之间兴趣相似度和社交影响力的拟合，为相应的常数系数，反映节点兴趣相似度和社交影响力所占的权重。2 社区划分方案社区Cx不能无限制地发展其社区成员，因此在进行社区决策时需要一些限制条件，以此来确定划分的社区个数以及每个社区中包含的节点个数。关于划分社区个数的问题，初始化k个社区，在社区划分层次遍历过程中，若两个社区中新遍历的待加入节点vi与vj直接相连，则将这两个社区合并为一个社区；若存在个相似的情况，则最终划分好的社区个数为k-=p。关于社区中包含节点个数的问题，首先给定一个社区中成员个数的上限lim，在层次遍历过程中，若一个社区中节点个数超过该上限值，则不再加入新的节点，终止对该社区的成员开发。也就是说，在社区成员开发的过程中，一个节点会被不同的社区竞争，而这个节点的最终归属权根据该节点在不同社区的标签传播值来确定，因为在层次遍历过程中，同一节点会因对应社区的不同拥有不用的标签传播值。假设节点vi对于分别从Cx和Cy遍历的两个社区，若从社区Cx遍历节点的标签传播值大于从Cy遍历的标签传播值，且社区Cx的成员个数未达到上限值，则节点vi从属于社区Cx，继续社区Cx的成员发展；若社区Cy的成员数未达上限，节点vi从属于社区Cy。96第 2 期张建伟，崔梦梦，蔡增玉：基于节点相似度与影响力的CCN社区划分方案基于特征向量中心性和改进标签传播算法划分的网络社区是非重叠的，且最终划分好的社区个数已知。根据描述，社区划分的伪码算法如算法1所示。算法1的时间复杂度取决于计算特征向量中心性值、特征向量中心性值排序、层次遍历、计算标签传播值和社区合并。其中，特征向量中心性值排序只需要找到前k个最大值，相当于Top k问题，算法时间复杂度为O（nlogk），其余部分的时间复杂度均为O（n）。由于这5个部分是串行工作的，因此算法1的时间复杂度为O（n）。算法1 社区划分算法输入：网络拓扑图G输出：划分好的社区结构1.FOR每个节点DO2.用式（3-7）计算特征向量中心性，并用式（3-8）标准化3.END4.降序排列特征向量中心性值5.选取前k个特征向量中心性值作为初始社区6.FOR每个初始社区DO7.用式（3-10）计算兴趣距离和社交距离的拟合8.用式（3-9）计算标签传播值9.END10.FOR每个当前社区DO11.IF两个初始社区相邻 THEN12.合并两个社区13.END14.IF社区内的节点数小于阈值lim THEN15.用式（3-7）计算邻居节点的标签传播值16.ELSE17.该社区划分完成18.END19.END3