社团融合事件的预测方法
社团融合事件的预测方法
【技术领域】
[0001] 本发明涉及数据挖掘领域，尤其涉及一种社团融合事件的预测方法。
【背景技术】
[0002] 在我们的生活中，复杂网络已经无处不在，其共同特点是规模巨大、结构复杂。例 如社交网络就是由实际生活中人与人之间关系构成的一种典型的复杂网络，其节点代表网 络用户或真实社会中的人，节点间的连接代表网络用户间的好友关系或真实的人际关系。 社交网络中这种由节点，和节点之间的连接形成的结构称为网络拓扑结构，该结构在不同 类型、不同阶段的社交网络中呈现出不同的特征。
[0003] 社团是代表复杂网络重要特征的一种子网络。社团同样具有网络拓扑结构，并且 社团结构会随着社团演化及其关键事件的发生呈现出不同的特征。复杂网络中关键事件的 发生代表着某种群体的行为导向。例如社交网络中的社团代表着各种社交圈，可以是朋友 圈、亲情圈、同事圈等等。这些社团可能意味着某些兴趣因素或社会因素的形成。对关键事 件进行预测有助于提前挖掘这些因素并加以利用，进一步指导网络行为。因此，对社团演化 关键事件的预测无论在研宄方面还是应用方面都有非常重要的意义。
[0004] 社团演化关键事件包括社团的消亡，新生，收缩，扩张，分裂和融合。目前，对社团 演化关键事件的预测方法已有一些研宄，但仅限于预测单个社团的演化倾向。社团融合事 件的发生涉及到多个社团，以往的研宄工作仅实现了对单个社团是否有融合倾向的预测， 并没有明确的方法来预测哪几个社团在未来的一段时间内会发生融合。
[0005] 综上，亟需一种方法来对将发生融合的社团进行更加详细的预测。
【发明内容】
[0006] 本发明所要解决的技术问题之一是提供一种方法来对将发生融合的社团进行更 加详细的预测。
[0007] 为了解决上述技术问题，本申请的实施例提供了一种社团融合事件的预测方法， 包括：步骤一、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据作 为训练数据；步骤二、对训练数据进行静态社团和动态社团的划分；步骤三、基于训练数据 提取任意两个社团之间的关键因素指标；步骤四、对所述关键因素指标进行监督训练，并根 据监督训练的学习结果判断任意两个社团是否会发生融合。
[0008] 优选地，关键因素指标包括两个社团之间的内部结构指标、所述内部结构指标的 一阶变化指标、二阶变化指标以及两个社团的外部结构相似度指标。
[0009] 优选地，利用如下表达式提取所述两个社团之间的内部结构指标：
[0011] 式中，Bd(i，j)为社团i与社团j之间的内部结构指标，Eu为社团i与社团j之 间的连接数，EjPL分别为社团i和社团j内部的连接数，N ^分别为社团i和社团j 内部的节点数。
[0012] 优选地，利用如下表达式提取所述两个社团的外部结构相似度指标：
[0014] 式中，Sim(i，j)为社团i与社团j的外部结构相似度指标；wi;k和w11;分别表示社 团i和社团k之间以及社团j和社团k之间的权，其中，
，Ei，k 和Eu分别为社团i与社团k之间以及社团j与社团k之间的连接数，N 和Nk分别为社 团i、社团j与社团k内部的节点数；m为社团序号数。
[0015] 优选地，步骤四中包括以下步骤：利用基于训练数据得到的关键因素指标构建预 测模型，并确定社团发生融合的分界线值；将基于距待预测的时间点最近的时间片的数据 得到的关键因素指标代入所述预测模型，并将得到的预测结果与所述分界线值进行比较以 判断社团是否会发生融合。
[0016] 优选地，利用如下表达式构建所述预测模型：
[0018] 式中，W,。为社团i与社团j之间发生融合事件的倾向度，
为概率拟合函数，
和
分别为社团i与社团j之间的内部结构指标的一阶变化指标、二阶变化指标 以及外部结构相似度指标；tjPtt分别表示不同的时间点，△t为时间间隔。
[0019] 优选地，在确定社团发生融合的分界线值的步骤中包括：将根据所述预测模型预 测得到的倾向度值进行归一化处理；利用处理后的倾向度值与基于训练数据提取得到的社 团融合情况建立基准函数；将基准函数取得最大值时的倾向度值作为社团发生融合的分界 线值。
[0020] 优选地，基准函数根据如下表达式建立：
[0024] 式中，F为基准函数，a和0为参数，T%为基于训练数据提取得到的发生融合的 社团对所对应的倾向度值。
[0025] 优选地，步骤四包括以下步骤：将基于训练数据得到的关键因素指标组成的向量 代入SVM预测模型进行训练以确定社团发生融合的分类器；将基于距待预测的时间点最近 的时间片的数据得到的关键因素指标组成的向量代入所述SVM预测模型，并根据得到的分 类预测结果判断社团是否会发生融合。
[0026] 优选地，在步骤三之前还包括：基于所述静态社团和所述动态社团对每一个社团 分别进行预测，得到将会参与融合的社团集合；在步骤三中，基于训练数据提取所述社团集 合中任意两个社团之间的关键因素指标。
[0027] 与现有技术相比，上述方案中的一个或多个实施例可以具有如下优点或有益效 果：
[0028] 通过提取两个社团之间的关键因素指标，实现了对任意两个社团或多个社团是否 会发生融合事件的预测，该方法预测可靠性高，可普适于绝大多数有权或无权的复杂网络 的分析。
[0029] 本发明的其他优点、目标，和特征在某种程度上将在随后的说明书中进行阐述，并 且在某种程度上，基于对下文的考察研宄对本领域技术人员而言将是显而易见的，或者可 以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书，权利要 求书，以及附图中所特别指出的结构来实现和获得。
【附图说明】
[0030] 附图用来提供对本申请的技术方案或现有技术的进一步理解，并且构成说明书的 一部分。其中，表达本申请实施例的附图与本申请的实施例一起用于解释本申请的技术方 案，但并不构成对本申请技术方案的限制。
[0031] 图1为本申请实施例的社团融合事件的预测方法的流程示意图；
[0032] 图2为内部结构指标累积分布曲线图；
[0033] 图3为外部结构相似度指标累积分布曲线图；
[0034] 图4为本申请实施例的利用关键因素指标进行监督训练的流程示意图；
[0035] 图5为本申请实施例的社团融合事件的预测方法的流程示意图。
【具体实施方式】
[0036] 以下将结合附图及实施例来详细说明本发明的实施方式，借此对本发明如何应用 技术手段来解决技术问题，并达成相应技术效果的实现过程能充分理解并据以实施。本申 请实施例以及实施例中的各个特征，在不相冲突前提下可以相互结合，所形成的技术方案 均在本发明的保护范围之内。
[0037] 另外，附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统 中执行。并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的 顺序执行所示出或描述的步骤。
[0038] 对于出现在本申请中的一些领域内常用语进行如下解释：
[0039] 网络拓扑结构：网络中由节点和节点间的连接组成的结构称为网络拓扑结构。
[0040] 网络社团：借助数学中的图论等工具研宄复杂网络。给定图G，网络社团是一个各 点紧密相连的子图G'。社团结构最直观的量化方法是网络社团内部密度大于外部密度。
[0041] 时间片：即在固定某一个时间点时对网络进行快照，如同对不断变化发展的网络 在某个时间点进行切片，称为时间片。
[0042] 静态社团：在某个时间片划分出来的社团。
[0043] 动态社团：将在一系列时间片划分出来的静态社团按照时间先后顺序连接起来形 成的社团演化轨迹。
[0044] 社团融合事件：两个及以上数目的社团中的节点在未来的某个时间被检测到连通 于一个社团中。
[0045] 监督训练：即根据训练集输入输出数据进行迭代计算得到分类、预测等模型。
[0046] 训练数据：用来得到训练模型的历史数据。
[0047] 图1为本申请实施例的社团融合事件的预测方法的流程示意图。该方法包括：步 骤S110、将网络原始数据按照设定的 时间片进行分割，并从中选取多个时间片数据作为训 练数据；步骤S120、对训练数据进行静态社团和动态社团的划分；步骤S130、基于训练数据 提取任意两个社团之间的关键因素指标；步骤S140、对所述关键因素指标进行监督训练， 并根据监督训练的学习结果判断任意两个社团是否会发生融合。
[0048] 本发明基于节点级别链路预测的思想提出了一种社团级别链路预测的方法来对 社团融合事件进行判断。网络中节点级别链路预测是指通过已知的网络结构等信息，预 测该网络中任意两个无连接的节点之间在将来的某段时间内产生连接的可能性。具体为， 选取一个位于待预测时间点之前的，且距离待预测时间点较近的时刻定义为当前时间tQ， 选取h之前的某一时间点t' (t'ctj，以[t'，、]时间范围内的原始数据，以及基于 [t'，、）时间范围内的原始数据所提取的指标数据作为训练数据，并利用选定的时间间隔 对上述时间范围内的原始数据进行时间片分割。
[0049] 在本申请的一个实施例中，筛选原始数据时要应尽可能选取与待预测时间点相接 近的历史数据。这是因为实际中的网络行为通常表现为短期的规律性，即一个网络在将来 某个时刻所呈现的状态主要与该时刻较接近的时间段内的因素的影响有关。因此，一般取 待预测时间点之前4-7个时间片的原始数据作为训练数据，以避免引入大量的无效数据而 影响预测效果，对原始数据的范围进行限定，保证数据的有效性。举例而言，要对新浪微博 的互粉关系的建立这个事件进行预测，分割所用的时间间隔在3~20天的范围内自定义。 具体的，待预测的时间点为2013年5月15日，原始数据包含3. 3万用户id和365万例用户 之间的互粉关系数据，具体为新浪微博互粉关系的形成时间。原始数据的时间跨度为2010 年11月~2013年11月，从原始数据中选取2013年3月15日至2013年5月1日这段时 间内的数据作为训练数据，选取时间间隔为At= 15天。将距待预测时间点一个时间间隔 之前的2013年5月1日设为当前时间h。利用At对上述时间范围内的训练数据进行时 间片分割，可以得到时间片分别为2013年5月1日，2013年4月15日，2013年4月1日和 2013年3月15日。
[0050] 接下来，基于选取的训练数据进行静态社团和动态社团的挖掘。静态社团划分的 目的是确定各时间片的社团状态。静态社团的划分可以用于后续动态社团的提取，同时静 态社团的划分有利于提取社团之间的参数关系。
[0051]在本申请的一个实施例中，采用了Fast-Unfolding算法进行静态社团的挖掘。Fast-Unfolding算法是基于模块度的静态社团挖掘算法，该算法基于复杂网络的自相似 性，并且对每次迭代划分出来的社团采用了层级的概念，可以在极短的时间内展现出来完 整的分层级的社团结构。它的输出结果包含了每一步迭代计算后的的社团挖掘结果，以便 于根据需求选择某一次迭代后的结果。该算法的具体过程包括，首先把网络中的每一个节 点都看做一个独立的社团并对其进行编号。然后，对于每个节点，考虑它的每一个邻居节 点，分别计算把该节点从自己原本所属的社团中删掉，并和其邻居节点所在的社团绑定在 一起以后的模块度，通过比较各模块度的值，将该节点绑定在模块度的增长最大的社团中。 通过对每个节点顺序、反复执行上述过程，直至无法再得到模块度的提升为止。接下来，通 过把已经挖掘出的社团看做节点，建立一个新的网络，并利用前面的迭代方法继续迭代。其 中，新节点之间的权重由新节点所代表的社团之间的连接的权重总和来代替。同一个社团 内的节点之间的连接构成了新网络中的节点自环。最终当模块度不再增长时，即网络的社 团结构不再变化时迭代停止。Fast-Unfolding算法的可操作性强，同时由于该算法的复杂 度是线性的，所以运行速度极快。
[0052] 需要说明的是，在本申请的其他实施例中，还可以采用其他的基于模块度的静态 社团挖掘方法，例如Newman贪婪算法、Newman快速算法等。通过对静态社团进行划分可以 得到与各时间片相对应的静态社团集合。
[0053] 社团演化关键事件的发生将使社团的结构在不同时间片具有不同的状态。用动态 社团表示某一社团在一系列时间片上的状态的集合。集合中的各个状态按照动态社团的演 化轨迹的先后顺序进行组织。动态社团的挖掘一般基于静态社团的划分结果进行。具体 为，对于任意两个相邻时间片t和t+1，将时间片t的静态社团Ct与时间片t+1的静态社团 Ct+1进行匹配，并将满足一定相似条件的Ct+1加入Ct所在的动态社团演化序列中，反复执行 上述过程提取动态社团的演化轨迹。
[0054]在本申请的一个实施例中，采用了Louvain算法进行动态社团的挖掘。该算法在 初始化动态社团集合时，为训练数据中与最早的时间片对应的静态社团集合中的每个社 团建立一个以其为起始社团的动态社团演化序列。在对两个静态社团进行匹配时，使用 Jaccard相似性系数来判断两个社团是否匹配，当Jaccard相似性系数大于选定的匹配阈 值时（例如取〇. 3)，认为两个社团匹配，并将匹配成功的社团加入以对应的匹配社团为起 始社团的动态社团演化序列中最后的位置。当Jaccard相似性系数小于或等于选定的匹配 阈值时，认为两个社团不匹配，并为这个没有匹配成功的社团生成一个新的演化社团序列。 若出现两个以上社团与某演化社团序列匹配，则生成一个新的演化社团序列，在该匹配时 刻之前两个社团序列的成员完全相同。
[0055]举例而言，基于新浪围脖的训练数据进行社团挖掘，可得到静态社团的数据文件 为"merge_yyyymmdd.comm"，且将每个时间片的数据分别存储在一个数据文件中。该数据文 件中的每一行代表一个社团，每行由属于该社团的各节点编号数据组成。同时可得到动态 社团的数据文件为"merge_yyyyddmm_4/15.timeline"，其中4代表以h为当前时间的该条 Timeline共取了 4个时间片，15代表时间片间隔At为15天。该数据文件中的数据格式为 "动态社团编号1 :时间片编号1 =静态社团编号1，时间片编号2 =静态社团编号2,……" 的形式。
[0056]需要说明的是，在本申请的其他实施例中，还可以采用不同的动态社团提取方法， 例如Louvain算法，FEDN算法等。根据挖掘得到的静态社团和动态社团可以方便地提取tQ 时刻的社团融合事件。具体为，若在时间片At的两个不同的动态社团DjPDj在时间 片h匹配到同一个社团，则称这两个动态社团融合。基于挖掘得到的社团还可以方便地从 训练数据中提取预测指标。
[0057]预测指标应该尽可能地表现训练数据中所包含的规律。现有技术中在进行预测指 标的提取时，是以单个社团为提取对象的，因此利用指标进行预测时得到的也是单个社团 是否参与到社团融合事件中，而不能对哪些社团之间将发生融合进行预测。为解决上述技 术问题，在本发明中，针对网络中任意一对社团来提取预测指标，提取到的指标与一对社团 的网络拓扑结构有关，预测结果为一对社团是否会发生融合。
[0058] 具体地，在本申请的实施例中，提取了多个影响两个社团是否会融合的预测指标， 将它们统一定义为关键因素指标，根据不同的指标影响社团是否会融合的作用不同，分为 直接因素指标和间接因素指标。进一步地，直接因素指标包括两个社团之间的内部结构指 标，以及内部结构指标的一阶变化指标和二阶变化指标，间接因素指标包括两个社团的外 部结构相似度指标。以下将分别介绍。
[0059] 社团i与社团j之间的内部结构指标Bd定义为：
[0061]式中，Eu代表社团i与社团j之间的连接数，EdPI分别代表社团i和社团j的 内部连接数，队和^分别代表社团i和社团j的内部节点数。
[0062] 具体的，根据社团的定义及其网络结构可以初步判定，对于给定的两个社团，社团 间连接数越多，社团融合的可能性越大，社团内部密度越小，社团融合的可能性越大。
[0063] 图2为内部结构指标累积分布曲线图。在任取的时间点t^At，提取该时间片任 意两社团间的内部结构指标，并观察其在时间点h的融合情况。之后分别针对融合的社团 对和未融合的社团对绘制内部结构指标的累积分布曲线（⑶F，CumulativeDistribution Function)，图中曲线1表示未发生融合的社团对的内部结构指标的累积分布曲线，曲线2 表示发生融合的社团对的内部结构指标的累积分布曲线。从图2中可以看 出，内部结构指 标值在融合社团对中的取值范围集中于1~15,而在未融合社团对中的取值范围集中于 0~0. 5。说明该内部结构指标可以有效地区分融合社团与非融合社团。
[0064] 进一步地，Bd的值越大表示社团融合的可能性越大，而Bd的一阶变化ABd代表Bd 随着时间发展的增速，增速越大，说明社团融合的趋势越明显。Bd的二阶变化△ABd也是同 样的道理。因此，根据Bd定义其一阶变化指标ABd和二阶变化指标AABd。如表达式（2)、 (3)所示：
[0067] 式中
分别表示时间为tfAt时的社 团i与社团j之间的内部结构指标及其一阶变化指标和二阶变化指标。其中，二阶变化指 标可以进一步表示为表达式（4)的形式：
[0069] 因此，在本申请的实施例中，应用上述直接因素指标进行预测时，需要选取四个时 间片的数据作为训练数据，分别为h、tfAt、h-2At和h-3At。
[0070] 提取间接因素指标时，应用了节点之间的局部结构相似度的提取方法。预测两个 节点之间产生连接的可能性的指标为两个节点叫和\之间的结构相似度，如表达式（5)所 示：
[0072] 式中，Wij为节点ni和节点nj之间连接的权值，若为无权网络，则该权值为1。若 节点叫和节点n」之间无连接，则wu的值为0。
[0073] 在本申请的实施例中，通过定义两个社团之间的权值来提取两个社团之间的外部 结构相似度指标。具体地，社团i与社团j之间的权值Wu如表达式（6)所示：
[0075] 式中，Eg代表社团i与社团j之间的连接数，N \分别代表社团i和社团j内 部的节点数。
[0076] 权值用来衡量忽略了具体的内部结构的社团之间的关系权值。社团间连接数 越多权值越大，且在社团间连接数一定的情况下，社团本身节点数越少社团间的权值相对 较大。
[0077] 最终得到的社团i与社团j之间的外部结构相似度指标如表达式（7)所示，其中 m表示社团序号数，
[0079] 图3为外部结构相似度指标累积分布曲线图。采用与建立内部结构指标的CDF曲 线类似的方法，建立外部结构相似度指标的CDF曲线。图中曲线1表示未发生融合的社团 对的内部结构指标的累积分布曲线，曲线2表示发生融合的社团对的内部结构指标的累积 分布曲线。从图3中可以看出，外部结构相似度指标值在融合社团对中的取值范围集中于 0. 00015~0. 006之间，而在未融合社团对中的取值大部分为0。即外部结构相似度指标取 值较大时，社团发生融合的概率较高，该指标可以有效区分融合社团和未融合社团。
[0080] 上述各直接因素指标以及间接因素指标，都是经过试验验证得到的符合理论分析 与实际操作的结果。既充分考虑了社团之间的主要影响因素和次要影响因素，又易于计算 和实现。其中，直接因素指标完全基于链路的结构特性进行定义，具有普适性，可以直接应 用于复杂网络的分析中。间接因素指标建立在社交网络具有好友关系属性的基础上。如果 两个陌生人有很多共同的朋友，则这两个陌生人成为朋友的可能性会大一些，因此对于社 交网络的融合事件的预测可以取得很好的效果。
[0081] 接下来，基于上述关键因素指标进行监督训练来判断任意两个社团是否将发生融 合。在本申请的一个实施例中，利用关键因素指标进行监督训练的过程如图4所示，包括： 步骤S410、利用基于训练数据得到的关键因素指标构建预测模型，并确定社团发生融合的 分界线值；步骤S420、将基于距待预测的时间点最近的时间片的数据得到的关键因素指标 代入所述预测模型，并将得到的预测结果与所述分界线值进行比较以判断社团是否会发生 融合。
[0082] 具体的，先建立内部结构指标与社团发生融合的概率之间的概率拟合函数。用函 数R(i,j)来表示社团的融合情况，当社团i与社团j在h时刻融合时，R(i,j)取1，当社 团i与社团j在h时刻未融合时，R(i，j)取0,可以用表达式（8)来表示：
[0084] 则当tQ-At时刻，且当此时的内部结构指标A(z'，&为BD。时，社团i与社团j在h时刻将要发生融合的概率如表达式（9)所示：
[0086] 式中，
值为BD。的t。时刻 发生融合的社团对数，
值为BDM%时 刻所有社团对数。进一步地，根据一系列的
值得到一系列的条件概率
的值，对它们进行概率函数拟合，得概率拟合函数
。举例而言，在基于新浪微博的历史数据进行函数拟合时， 得到的概率拟合函数具有如表达式（10)所示的形式：
[0088] 其中，a、b、I；为利用训练数据在拟合过程中所产生的概率函数的参数，且a =-〇. 5、b= 0. 038、TQ= 0. 03。
[0089] 进一步地，利用得到的概率拟合函数、结合内部结构指标的一阶变化指标、二阶变 化指标以及两个社团的外部结构相似度指标构建预测模型，如表达式（11)所示：
[0091] 式中，表示t。时刻社团i与社团j之间发生融合事件的倾向度。根据之前建 立的内部结构指标与社团融合的概率函数关系，并根据之前的分析，ABd和△ABd越大，社 团融合可能性越大，大致确定预测模型与Bd、ABd和AABd之间的关系。进一步地，在内部 结构指标一定的基础上，外部结构相似度指标值越大，社团融合可能性越大。因此，构建了 用来衡量社团融合倾向度的预测模型。另外需要说明的是，预测模型并不唯一。
[0092] 利用预测模型与训练数据确定社团发生融合的分界线值，包括，将根据预测模型 预测得到的倾向度值进行归一化处理，利用处理后的倾向度值与基于训练数据提取得到的 社团融合情况建立基准函数，将基准函数取得最大值时的倾向度值作为社团发生融合的分 界线值。
[0093] 具体的，对表达式（11)的倾向度进行归一化可得表达式（12):
[0095] 将得到的对于、时间片的预测结果按照归一化后的倾向度降序排列，并与％时刻 的社团融合的真实情况进行对比来建立基准函数。对于每对被正确预测为将发生融合的社 团所对应的倾向度值TDd，进行如下计算：
[0098] 式中，1%为基于训练数据提取得到的发生融合的社团对所对应的倾向度值。进一 步地，根据表达式（13)建立基准函数，并将表达式（13)取得最大值时的T%的值作为判定 社团是否将会发生融合的分界线值diV(l。
[0100] 选取diV(l时希望选取的值对应a和0的值大小相对均衡，因此基准函数F值的 计算取a和0的调合平均数。
[0101] 在得到预测模型和判定社团是否将会发生融合的分界线值之后，便可以根据当前 时刻h的训练数据预测时间为tt时刻的社团的融合情况，具体包括：基于h时刻的训 练数据提取关键因素指标，以所得到的关键因素指标作为预测模型的输入数据代入表达式 (11)的预测模型，并将根据表达式（12)得到的归一化的预测结果
与社团融合 分界线值虹^进行比较以判断社团是否将发生融合。具体的，当
时，对 应的社团对的预测结果为将发生融合，反之则预测为不发生融合。
[0102] 根据本申请的实施例，基于预测到的将发生融合的社团对，可以进一步推出一个 具体的融合事件由哪几个社团构成。例如若预测社团i与社团j将发生融合，社团j与社 团k将发生融合，社团k与社团i将发生融合，那么社团i、j、k就构成了一个融合事件。通 过预测任意两个社团之间的融合行为，有效地缩小了观察范围，降低了大数据在进行社团 融合分析时的难度。
[0103] 举例而言，在上述对新浪微博进行预测的示例中，通过计算a、0及F，可以得到 使F取得最大值0.13时的TD。的值为0.1247,将0.1247作为判定社团是否将会发生融合 的分界线值。当通过预测模型得到的TcLw大于0. 1247时，对应的社团对的预测结果为将 发生融合，当Td_g/j、于等于0. 1247时，对应的社团对的预测结果为不发生融合。
[0104] 基于训练数据建立的预测模型对社团的融合行为进行预测的方法是一种有监督 的训练方法，同时实验数据表明，实现该功能的准确率和召回率是效果很好的，可以支撑相 关的实际应用，且为社团演化方面的进一步研宄提供了便利。
[0105] 当然，在通过监督训练判断任意两个社团是否将发生融合时，还可以使用现有的 预测模型进行训练和预测。在本申请的其他实施例中，采用SVM模 型进行预测，实施过程 为：先将基于训练数据得到的关键因素指标组成的向量代入SVM预测模型进行训练以确 定社团发生融合的分类器；再将基于距待预测的时间点最近的时间片的数据得到的关键 因素指标组成的向量代入所述SVM预测模型，并根据得到的分类预测结果判断社团是否 会发生融合。具体的，记At时间片社团(^和q之间的直接因素指标分别为内部结构
，间接因 素为社团的外部结构相似度
> 将这四个参数分别进行归一化处理，则该模块 所使用的第n条训练集输入变量为
[0107] 第n条训练集数据输出变量为
[0108] 进一步地，将所有的训练集输入、输出变量代入分类器中，可以训练得到分类模型 即超平面，然后代入归一化后的h时间片的预测输入数据，其中第n条预测输入数据输入 变量为
[0110] 将其带入分类模型中根据计算结果为+1或-1即可得知该数据在超平面的哪一 侦牝即其预测结果为，在△t时刻社团是否会融合。
[0111] 需要说明的是，在真实的社交网络中，社团未融合事件远远多于社团融合事件，因 此采集的到的初始训练集中未融合社团样本量远多于融合社团样本量。因此，采用本申请 实施例所建立的倾向度模型对于任意的关键因素指标值均可得到社团融合倾向度值，且得 到的社团融合倾向度值具有明显的区分度。而SVM模型的预测结果会倾向样本多的类，会 出现预测出的融合社团个数为零的情况。若对样本进行抽样以达到两类样本量均衡，则会 大大降低样本数据质量，得到的训练模型也会严重失真。
[0112] 另外，前面的预测方法都是直接对任意两个社团之间是否将会发生融合进行预测 的，但显然地，预测哪两个社团将发生融合，或是哪些社团将发生融合，都是基于社团自身 具有发生融合的可能性的基础之上的，因此，在本申请的另一个实施例中，通过先对单个社 团是否具有参与融合的可能性进行判断，进一步缩小预测的范围，如图5所示，该方法包 括：步骤S510、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据 作为训练数据；步骤S520、对训练数据进行静态社团和动态社团的划分；步骤S530、基于所 述静态社团和所述动态社团对每一个社团分别进行预测，得到将会参与融合的社团集合； 步骤S540、基于训练数据提取所述社团集合中任意两个社团之间的关键因素指标；步骤 S550、对所述关键因素指标进行监督训练，并根据监督训练的学习结果判断任意两个社团 是否会发生融合。
[0113] 具体地，在基于所述静态社团和所述动态社团对每一个社团分别进行预测的步骤 中，可以采用现有技术中的预测单个社团是否会参与融合的任何方法来实现。举例而言，采 用现有的SVM支持向量机的分类算法，对于时间片的各社团，提取三个基本指标：社 团大小、社团的内部边和社团节点度总和的比值（In-Degree)、以及社团在时间片tQ_At时 与在时间片h-2At时的Jaccard相似系数，及这三个指标的"一阶变化指标"和"二阶变 化指标"。观察这些社团在h时间片是否与其他社团发生融合事件（融合记为1，不融合记 为-1)。将以上指标和融合结果代入SVM分类器进行训练得到预测模型。同样，取h时间 片的社团的各指标，代入预测模型中，分类结果为"1"，则预测结果为该社团即将与其他社 团发生融合事件，相反若分类结果为"-1"，则预测结果为该社团不会与其他社团发生融合 事件。由此确定将会参与融合的社团的集合，这样在基于上述集合建立关键因素指标时，可 以极大地减少工作量，提高预测效率。
[0114] 本申请实施例的社团融合预测方法可以应用与有权网络的预测，具有更加普遍的 应用范围。通过定义任意两个社团之间的关键因素指标，实现对两个社团之间或多个社团 之间的融合行为的有效预测。
[0115] 虽然本发明所揭露的实施方式如上，但所述的内容只是为了便于理解本发明而采 用的实施方式，并非用以限定本发明。任何本发明所属技术领域内的技术人员，在不脱离本 发明所揭露的精神和范围的前提下，可以在实施的形式上及细节上作任何的修改与变化， 但本发明的专利保护范围，仍须以所附的权利要求书所界定的范围为准。
【主权项】
1. 一种社团融合事件的预测方法，包括： 步骤一、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据作 为训练数据； 步骤二、对训练数据进行静态社团和动态社团的划分； 步骤三、基于训练数据提取任意两个社团之间的关键因素指标； 步骤四、对所述关键因素指标进行监督训练，并根据监督训练的学习结果判断任意两 个社团是否会发生融合。2. 根据权利要求1所述的方法，其特征在于， 所述关键因素指标包括两个社团之间的内部结构指标、所述内部结构指标的一阶变化 指标、二阶变化指标以及两个社团的外部结构相似度指标。3. 根据权利要求2所述的方法，其特征在于，利用如下表达式提取所述两个社团之间 的内部结构指标：式中，Bd(i，j)为社团i与社团j之间的内部结构指标，Eu为社团i与社团j之间的 连接数，EjP L分别为社团i和社团j内部的连接数，N JP \分别为社团i和社团j内部 的节点数。4. 根据权利要求2所述的方法，其特征在于，利用如下表达式提取所述两个社团的外 部结构相似度指标：式中，Sim(i, j)为社团i与社团j的外部结构相似度指标；wi;k和w j，k分别表示社团i 和社团k之间以及社团j和社团k之间的权，其中，， Ej;k分别为社团i与社团k之间以及社团j与社团k之间的连接数，N 和Nk分别为社团 i、社团j与社团k内部的节点数;m为社团序号数。5. 根据权利要求2所述的方法，其特征在于，在所述步骤四中包括以下步骤： 利用基于训练数据得到的关键因素指标构建预测模型，并确定社团发生融合的分界线 值； 将基于距待预测的时间点最近的时间片的数据得到的关键因素指标代入所述预测模 型，并将得到的预测结果与所述分界线值进行比较以判断社团是否会发生融合。6. 根据权利要求5所述的方法，其特征在于，利用如下表达式构建所述预测模型：式中，以，,，为社团i与社团j之间发生融合事件的倾向度，为概率拟合函数，和 V分别为社团i与社团j之间的内部结构指标的一阶变化指标、二阶变化指标 以及外部结构相似度指标；tjP t ^ △ t分别表示不同的时间点，△ t为时间间隔。7. 根据权利要求5或6所述的方法，其特征在于，在确定社团发生融合的分界线值的步 骤中包括： 将根据所述预测模型预测得到的倾向度值进行归一化处理； 利用处理后的倾向度值与基于训练数据提取得到的社团融合情况建立基准函数； 将基准函数取得最大值时的倾向度值作为社团发生融合的分界线值。8. 根据权利要求7所述的方法，其特征在于，所述基准函数根据如下表达式建立：式中，F为基准函数，α和β为参数，TDtlS基于训练数据提取得到的发生融合的社团 对所对应的倾向度值。9. 根据权利要求1所述的方法，其特征在于，步骤四包括以下步骤： 将基于训练数据得到的关键因素指标组成的向量代入SVM预测模型进行训练以确定 社团发生融合的分类器； 将基于距待预测的时间点最近的时间片的数据得到的关键因素指标组成的向量代入 所述SVM预测模型，并根据得到的分类预测结果判断社团是否会发生融合。10. 根据权利要求1所述的方法，其特征在于，在步骤三之前还包括： 基于所述静态社团和所述动态社团对每一个社团分别进行预测，得到将会参与融合的 社团集合； 在步骤三中，基于训练数据提取所述社团集合中任意两个社团之间的关键因素指标。
【专利摘要】本发明公开了一种社团融合事件的预测方法，包括：步骤一、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据作为训练数据；步骤二、对训练数据进行静态社团和动态社团的划分；步骤三、基于训练数据提取任意两个社团之间的关键因素指标；步骤四、对所述关键因素指标进行监督训练，并根据监督训练的学习结果判断任意两个社团是否会发生融合。该方法实现了对任意两个社团或多个社团是否会发生融合事件的预测，预测可靠性高，可普适于绝大多数有权或无权的复杂网络的分析。
【IPC分类】G06K9/62, G06Q50/00, G06Q10/04
【公开号】CN104899657
【申请号】CN201510314273
【发明人】唐晓晟, 李巍, 胡铮, 张诗悦
【申请人】北京邮电大学
【公开日】2015年9月9日
【申请日】2015年6月9日
【技术领域】
[0001] 本发明涉及数据挖掘领域，尤其涉及一种社团融合事件的预测方法。
【背景技术】
[0002] 在我们的生活中，复杂网络已经无处不在，其共同特点是规模巨大、结构复杂。例 如社交网络就是由实际生活中人与人之间关系构成的一种典型的复杂网络，其节点代表网 络用户或真实社会中的人，节点间的连接代表网络用户间的好友关系或真实的人际关系。 社交网络中这种由节点，和节点之间的连接形成的结构称为网络拓扑结构，该结构在不同 类型、不同阶段的社交网络中呈现出不同的特征。
[0003] 社团是代表复杂网络重要特征的一种子网络。社团同样具有网络拓扑结构，并且 社团结构会随着社团演化及其关键事件的发生呈现出不同的特征。复杂网络中关键事件的 发生代表着某种群体的行为导向。例如社交网络中的社团代表着各种社交圈，可以是朋友 圈、亲情圈、同事圈等等。这些社团可能意味着某些兴趣因素或社会因素的形成。对关键事 件进行预测有助于提前挖掘这些因素并加以利用，进一步指导网络行为。因此，对社团演化 关键事件的预测无论在研宄方面还是应用方面都有非常重要的意义。
[0004] 社团演化关键事件包括社团的消亡，新生，收缩，扩张，分裂和融合。目前，对社团 演化关键事件的预测方法已有一些研宄，但仅限于预测单个社团的演化倾向。社团融合事 件的发生涉及到多个社团，以往的研宄工作仅实现了对单个社团是否有融合倾向的预测， 并没有明确的方法来预测哪几个社团在未来的一段时间内会发生融合。
[0005] 综上，亟需一种方法来对将发生融合的社团进行更加详细的预测。
【发明内容】
[0006] 本发明所要解决的技术问题之一是提供一种方法来对将发生融合的社团进行更 加详细的预测。
[0007] 为了解决上述技术问题，本申请的实施例提供了一种社团融合事件的预测方法， 包括：步骤一、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据作 为训练数据；步骤二、对训练数据进行静态社团和动态社团的划分；步骤三、基于训练数据 提取任意两个社团之间的关键因素指标；步骤四、对所述关键因素指标进行监督训练，并根 据监督训练的学习结果判断任意两个社团是否会发生融合。
[0008] 优选地，关键因素指标包括两个社团之间的内部结构指标、所述内部结构指标的 一阶变化指标、二阶变化指标以及两个社团的外部结构相似度指标。
[0009] 优选地，利用如下表达式提取所述两个社团之间的内部结构指标：
[0011] 式中，Bd(i，j)为社团i与社团j之间的内部结构指标，Eu为社团i与社团j之 间的连接数，EjPL分别为社团i和社团j内部的连接数，N ^分别为社团i和社团j 内部的节点数。
[0012] 优选地，利用如下表达式提取所述两个社团的外部结构相似度指标：
[0014] 式中，Sim(i，j)为社团i与社团j的外部结构相似度指标；wi;k和w11;分别表示社 团i和社团k之间以及社团j和社团k之间的权，其中，
，Ei，k 和Eu分别为社团i与社团k之间以及社团j与社团k之间的连接数，N 和Nk分别为社 团i、社团j与社团k内部的节点数；m为社团序号数。
[0015] 优选地，步骤四中包括以下步骤：利用基于训练数据得到的关键因素指标构建预 测模型，并确定社团发生融合的分界线值；将基于距待预测的时间点最近的时间片的数据 得到的关键因素指标代入所述预测模型，并将得到的预测结果与所述分界线值进行比较以 判断社团是否会发生融合。
[0016] 优选地，利用如下表达式构建所述预测模型：
[0018] 式中，W,。为社团i与社团j之间发生融合事件的倾向度，
为概率拟合函数，
和
分别为社团i与社团j之间的内部结构指标的一阶变化指标、二阶变化指标 以及外部结构相似度指标；tjPtt分别表示不同的时间点，△t为时间间隔。
[0019] 优选地，在确定社团发生融合的分界线值的步骤中包括：将根据所述预测模型预 测得到的倾向度值进行归一化处理；利用处理后的倾向度值与基于训练数据提取得到的社 团融合情况建立基准函数；将基准函数取得最大值时的倾向度值作为社团发生融合的分界 线值。
[0020] 优选地，基准函数根据如下表达式建立：
[0024] 式中，F为基准函数，a和0为参数，T%为基于训练数据提取得到的发生融合的 社团对所对应的倾向度值。
[0025] 优选地，步骤四包括以下步骤：将基于训练数据得到的关键因素指标组成的向量 代入SVM预测模型进行训练以确定社团发生融合的分类器；将基于距待预测的时间点最近 的时间片的数据得到的关键因素指标组成的向量代入所述SVM预测模型，并根据得到的分 类预测结果判断社团是否会发生融合。
[0026] 优选地，在步骤三之前还包括：基于所述静态社团和所述动态社团对每一个社团 分别进行预测，得到将会参与融合的社团集合；在步骤三中，基于训练数据提取所述社团集 合中任意两个社团之间的关键因素指标。
[0027] 与现有技术相比，上述方案中的一个或多个实施例可以具有如下优点或有益效 果：
[0028] 通过提取两个社团之间的关键因素指标，实现了对任意两个社团或多个社团是否 会发生融合事件的预测，该方法预测可靠性高，可普适于绝大多数有权或无权的复杂网络 的分析。
[0029] 本发明的其他优点、目标，和特征在某种程度上将在随后的说明书中进行阐述，并 且在某种程度上，基于对下文的考察研宄对本领域技术人员而言将是显而易见的，或者可 以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书，权利要 求书，以及附图中所特别指出的结构来实现和获得。
【附图说明】
[0030] 附图用来提供对本申请的技术方案或现有技术的进一步理解，并且构成说明书的 一部分。其中，表达本申请实施例的附图与本申请的实施例一起用于解释本申请的技术方 案，但并不构成对本申请技术方案的限制。
[0031] 图1为本申请实施例的社团融合事件的预测方法的流程示意图；
[0032] 图2为内部结构指标累积分布曲线图；
[0033] 图3为外部结构相似度指标累积分布曲线图；
[0034] 图4为本申请实施例的利用关键因素指标进行监督训练的流程示意图；
[0035] 图5为本申请实施例的社团融合事件的预测方法的流程示意图。
【具体实施方式】
[0036] 以下将结合附图及实施例来详细说明本发明的实施方式，借此对本发明如何应用 技术手段来解决技术问题，并达成相应技术效果的实现过程能充分理解并据以实施。本申 请实施例以及实施例中的各个特征，在不相冲突前提下可以相互结合，所形成的技术方案 均在本发明的保护范围之内。
[0037] 另外，附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统 中执行。并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的 顺序执行所示出或描述的步骤。
[0038] 对于出现在本申请中的一些领域内常用语进行如下解释：
[0039] 网络拓扑结构：网络中由节点和节点间的连接组成的结构称为网络拓扑结构。
[0040] 网络社团：借助数学中的图论等工具研宄复杂网络。给定图G，网络社团是一个各 点紧密相连的子图G'。社团结构最直观的量化方法是网络社团内部密度大于外部密度。
[0041] 时间片：即在固定某一个时间点时对网络进行快照，如同对不断变化发展的网络 在某个时间点进行切片，称为时间片。
[0042] 静态社团：在某个时间片划分出来的社团。
[0043] 动态社团：将在一系列时间片划分出来的静态社团按照时间先后顺序连接起来形 成的社团演化轨迹。
[0044] 社团融合事件：两个及以上数目的社团中的节点在未来的某个时间被检测到连通 于一个社团中。
[0045] 监督训练：即根据训练集输入输出数据进行迭代计算得到分类、预测等模型。
[0046] 训练数据：用来得到训练模型的历史数据。
[0047] 图1为本申请实施例的社团融合事件的预测方法的流程示意图。该方法包括：步 骤S110、将网络原始数据按照设定的 时间片进行分割，并从中选取多个时间片数据作为训 练数据；步骤S120、对训练数据进行静态社团和动态社团的划分；步骤S130、基于训练数据 提取任意两个社团之间的关键因素指标；步骤S140、对所述关键因素指标进行监督训练， 并根据监督训练的学习结果判断任意两个社团是否会发生融合。
[0048] 本发明基于节点级别链路预测的思想提出了一种社团级别链路预测的方法来对 社团融合事件进行判断。网络中节点级别链路预测是指通过已知的网络结构等信息，预 测该网络中任意两个无连接的节点之间在将来的某段时间内产生连接的可能性。具体为， 选取一个位于待预测时间点之前的，且距离待预测时间点较近的时刻定义为当前时间tQ， 选取h之前的某一时间点t' (t'ctj，以[t'，、]时间范围内的原始数据，以及基于 [t'，、）时间范围内的原始数据所提取的指标数据作为训练数据，并利用选定的时间间隔 对上述时间范围内的原始数据进行时间片分割。
[0049] 在本申请的一个实施例中，筛选原始数据时要应尽可能选取与待预测时间点相接 近的历史数据。这是因为实际中的网络行为通常表现为短期的规律性，即一个网络在将来 某个时刻所呈现的状态主要与该时刻较接近的时间段内的因素的影响有关。因此，一般取 待预测时间点之前4-7个时间片的原始数据作为训练数据，以避免引入大量的无效数据而 影响预测效果，对原始数据的范围进行限定，保证数据的有效性。举例而言，要对新浪微博 的互粉关系的建立这个事件进行预测，分割所用的时间间隔在3~20天的范围内自定义。 具体的，待预测的时间点为2013年5月15日，原始数据包含3. 3万用户id和365万例用户 之间的互粉关系数据，具体为新浪微博互粉关系的形成时间。原始数据的时间跨度为2010 年11月~2013年11月，从原始数据中选取2013年3月15日至2013年5月1日这段时 间内的数据作为训练数据，选取时间间隔为At= 15天。将距待预测时间点一个时间间隔 之前的2013年5月1日设为当前时间h。利用At对上述时间范围内的训练数据进行时 间片分割，可以得到时间片分别为2013年5月1日，2013年4月15日，2013年4月1日和 2013年3月15日。
[0050] 接下来，基于选取的训练数据进行静态社团和动态社团的挖掘。静态社团划分的 目的是确定各时间片的社团状态。静态社团的划分可以用于后续动态社团的提取，同时静 态社团的划分有利于提取社团之间的参数关系。
[0051]在本申请的一个实施例中，采用了Fast-Unfolding算法进行静态社团的挖掘。Fast-Unfolding算法是基于模块度的静态社团挖掘算法，该算法基于复杂网络的自相似 性，并且对每次迭代划分出来的社团采用了层级的概念，可以在极短的时间内展现出来完 整的分层级的社团结构。它的输出结果包含了每一步迭代计算后的的社团挖掘结果，以便 于根据需求选择某一次迭代后的结果。该算法的具体过程包括，首先把网络中的每一个节 点都看做一个独立的社团并对其进行编号。然后，对于每个节点，考虑它的每一个邻居节 点，分别计算把该节点从自己原本所属的社团中删掉，并和其邻居节点所在的社团绑定在 一起以后的模块度，通过比较各模块度的值，将该节点绑定在模块度的增长最大的社团中。 通过对每个节点顺序、反复执行上述过程，直至无法再得到模块度的提升为止。接下来，通 过把已经挖掘出的社团看做节点，建立一个新的网络，并利用前面的迭代方法继续迭代。其 中，新节点之间的权重由新节点所代表的社团之间的连接的权重总和来代替。同一个社团 内的节点之间的连接构成了新网络中的节点自环。最终当模块度不再增长时，即网络的社 团结构不再变化时迭代停止。Fast-Unfolding算法的可操作性强，同时由于该算法的复杂 度是线性的，所以运行速度极快。
[0052] 需要说明的是，在本申请的其他实施例中，还可以采用其他的基于模块度的静态 社团挖掘方法，例如Newman贪婪算法、Newman快速算法等。通过对静态社团进行划分可以 得到与各时间片相对应的静态社团集合。
[0053] 社团演化关键事件的发生将使社团的结构在不同时间片具有不同的状态。用动态 社团表示某一社团在一系列时间片上的状态的集合。集合中的各个状态按照动态社团的演 化轨迹的先后顺序进行组织。动态社团的挖掘一般基于静态社团的划分结果进行。具体 为，对于任意两个相邻时间片t和t+1，将时间片t的静态社团Ct与时间片t+1的静态社团 Ct+1进行匹配，并将满足一定相似条件的Ct+1加入Ct所在的动态社团演化序列中，反复执行 上述过程提取动态社团的演化轨迹。
[0054]在本申请的一个实施例中，采用了Louvain算法进行动态社团的挖掘。该算法在 初始化动态社团集合时，为训练数据中与最早的时间片对应的静态社团集合中的每个社 团建立一个以其为起始社团的动态社团演化序列。在对两个静态社团进行匹配时，使用 Jaccard相似性系数来判断两个社团是否匹配，当Jaccard相似性系数大于选定的匹配阈 值时（例如取〇. 3)，认为两个社团匹配，并将匹配成功的社团加入以对应的匹配社团为起 始社团的动态社团演化序列中最后的位置。当Jaccard相似性系数小于或等于选定的匹配 阈值时，认为两个社团不匹配，并为这个没有匹配成功的社团生成一个新的演化社团序列。 若出现两个以上社团与某演化社团序列匹配，则生成一个新的演化社团序列，在该匹配时 刻之前两个社团序列的成员完全相同。
[0055]举例而言，基于新浪围脖的训练数据进行社团挖掘，可得到静态社团的数据文件 为"merge_yyyymmdd.comm"，且将每个时间片的数据分别存储在一个数据文件中。该数据文 件中的每一行代表一个社团，每行由属于该社团的各节点编号数据组成。同时可得到动态 社团的数据文件为"merge_yyyyddmm_4/15.timeline"，其中4代表以h为当前时间的该条 Timeline共取了 4个时间片，15代表时间片间隔At为15天。该数据文件中的数据格式为 "动态社团编号1 :时间片编号1 =静态社团编号1，时间片编号2 =静态社团编号2,……" 的形式。
[0056]需要说明的是，在本申请的其他实施例中，还可以采用不同的动态社团提取方法， 例如Louvain算法，FEDN算法等。根据挖掘得到的静态社团和动态社团可以方便地提取tQ 时刻的社团融合事件。具体为，若在时间片At的两个不同的动态社团DjPDj在时间 片h匹配到同一个社团，则称这两个动态社团融合。基于挖掘得到的社团还可以方便地从 训练数据中提取预测指标。
[0057]预测指标应该尽可能地表现训练数据中所包含的规律。现有技术中在进行预测指 标的提取时，是以单个社团为提取对象的，因此利用指标进行预测时得到的也是单个社团 是否参与到社团融合事件中，而不能对哪些社团之间将发生融合进行预测。为解决上述技 术问题，在本发明中，针对网络中任意一对社团来提取预测指标，提取到的指标与一对社团 的网络拓扑结构有关，预测结果为一对社团是否会发生融合。
[0058] 具体地，在本申请的实施例中，提取了多个影响两个社团是否会融合的预测指标， 将它们统一定义为关键因素指标，根据不同的指标影响社团是否会融合的作用不同，分为 直接因素指标和间接因素指标。进一步地，直接因素指标包括两个社团之间的内部结构指 标，以及内部结构指标的一阶变化指标和二阶变化指标，间接因素指标包括两个社团的外 部结构相似度指标。以下将分别介绍。
[0059] 社团i与社团j之间的内部结构指标Bd定义为：
[0061]式中，Eu代表社团i与社团j之间的连接数，EdPI分别代表社团i和社团j的 内部连接数，队和^分别代表社团i和社团j的内部节点数。
[0062] 具体的，根据社团的定义及其网络结构可以初步判定，对于给定的两个社团，社团 间连接数越多，社团融合的可能性越大，社团内部密度越小，社团融合的可能性越大。
[0063] 图2为内部结构指标累积分布曲线图。在任取的时间点t^At，提取该时间片任 意两社团间的内部结构指标，并观察其在时间点h的融合情况。之后分别针对融合的社团 对和未融合的社团对绘制内部结构指标的累积分布曲线（⑶F，CumulativeDistribution Function)，图中曲线1表示未发生融合的社团对的内部结构指标的累积分布曲线，曲线2 表示发生融合的社团对的内部结构指标的累积分布曲线。从图2中可以看 出，内部结构指 标值在融合社团对中的取值范围集中于1~15,而在未融合社团对中的取值范围集中于 0~0. 5。说明该内部结构指标可以有效地区分融合社团与非融合社团。
[0064] 进一步地，Bd的值越大表示社团融合的可能性越大，而Bd的一阶变化ABd代表Bd 随着时间发展的增速，增速越大，说明社团融合的趋势越明显。Bd的二阶变化△ABd也是同 样的道理。因此，根据Bd定义其一阶变化指标ABd和二阶变化指标AABd。如表达式（2)、 (3)所示：
[0067] 式中
分别表示时间为tfAt时的社 团i与社团j之间的内部结构指标及其一阶变化指标和二阶变化指标。其中，二阶变化指 标可以进一步表示为表达式（4)的形式：
[0069] 因此，在本申请的实施例中，应用上述直接因素指标进行预测时，需要选取四个时 间片的数据作为训练数据，分别为h、tfAt、h-2At和h-3At。
[0070] 提取间接因素指标时，应用了节点之间的局部结构相似度的提取方法。预测两个 节点之间产生连接的可能性的指标为两个节点叫和\之间的结构相似度，如表达式（5)所 示：
[0072] 式中，Wij为节点ni和节点nj之间连接的权值，若为无权网络，则该权值为1。若 节点叫和节点n」之间无连接，则wu的值为0。
[0073] 在本申请的实施例中，通过定义两个社团之间的权值来提取两个社团之间的外部 结构相似度指标。具体地，社团i与社团j之间的权值Wu如表达式（6)所示：
[0075] 式中，Eg代表社团i与社团j之间的连接数，N \分别代表社团i和社团j内 部的节点数。
[0076] 权值用来衡量忽略了具体的内部结构的社团之间的关系权值。社团间连接数 越多权值越大，且在社团间连接数一定的情况下，社团本身节点数越少社团间的权值相对 较大。
[0077] 最终得到的社团i与社团j之间的外部结构相似度指标如表达式（7)所示，其中 m表示社团序号数，
[0079] 图3为外部结构相似度指标累积分布曲线图。采用与建立内部结构指标的CDF曲 线类似的方法，建立外部结构相似度指标的CDF曲线。图中曲线1表示未发生融合的社团 对的内部结构指标的累积分布曲线，曲线2表示发生融合的社团对的内部结构指标的累积 分布曲线。从图3中可以看出，外部结构相似度指标值在融合社团对中的取值范围集中于 0. 00015~0. 006之间，而在未融合社团对中的取值大部分为0。即外部结构相似度指标取 值较大时，社团发生融合的概率较高，该指标可以有效区分融合社团和未融合社团。
[0080] 上述各直接因素指标以及间接因素指标，都是经过试验验证得到的符合理论分析 与实际操作的结果。既充分考虑了社团之间的主要影响因素和次要影响因素，又易于计算 和实现。其中，直接因素指标完全基于链路的结构特性进行定义，具有普适性，可以直接应 用于复杂网络的分析中。间接因素指标建立在社交网络具有好友关系属性的基础上。如果 两个陌生人有很多共同的朋友，则这两个陌生人成为朋友的可能性会大一些，因此对于社 交网络的融合事件的预测可以取得很好的效果。
[0081] 接下来，基于上述关键因素指标进行监督训练来判断任意两个社团是否将发生融 合。在本申请的一个实施例中，利用关键因素指标进行监督训练的过程如图4所示，包括： 步骤S410、利用基于训练数据得到的关键因素指标构建预测模型，并确定社团发生融合的 分界线值；步骤S420、将基于距待预测的时间点最近的时间片的数据得到的关键因素指标 代入所述预测模型，并将得到的预测结果与所述分界线值进行比较以判断社团是否会发生 融合。
[0082] 具体的，先建立内部结构指标与社团发生融合的概率之间的概率拟合函数。用函 数R(i,j)来表示社团的融合情况，当社团i与社团j在h时刻融合时，R(i,j)取1，当社 团i与社团j在h时刻未融合时，R(i，j)取0,可以用表达式（8)来表示：
[0084] 则当tQ-At时刻，且当此时的内部结构指标A(z'，&为BD。时，社团i与社团j在h时刻将要发生融合的概率如表达式（9)所示：
[0086] 式中，
值为BD。的t。时刻 发生融合的社团对数，
值为BDM%时 刻所有社团对数。进一步地，根据一系列的
值得到一系列的条件概率
的值，对它们进行概率函数拟合，得概率拟合函数
。举例而言，在基于新浪微博的历史数据进行函数拟合时， 得到的概率拟合函数具有如表达式（10)所示的形式：
[0088] 其中，a、b、I；为利用训练数据在拟合过程中所产生的概率函数的参数，且a =-〇. 5、b= 0. 038、TQ= 0. 03。
[0089] 进一步地，利用得到的概率拟合函数、结合内部结构指标的一阶变化指标、二阶变 化指标以及两个社团的外部结构相似度指标构建预测模型，如表达式（11)所示：
[0091] 式中，表示t。时刻社团i与社团j之间发生融合事件的倾向度。根据之前建 立的内部结构指标与社团融合的概率函数关系，并根据之前的分析，ABd和△ABd越大，社 团融合可能性越大，大致确定预测模型与Bd、ABd和AABd之间的关系。进一步地，在内部 结构指标一定的基础上，外部结构相似度指标值越大，社团融合可能性越大。因此，构建了 用来衡量社团融合倾向度的预测模型。另外需要说明的是，预测模型并不唯一。
[0092] 利用预测模型与训练数据确定社团发生融合的分界线值，包括，将根据预测模型 预测得到的倾向度值进行归一化处理，利用处理后的倾向度值与基于训练数据提取得到的 社团融合情况建立基准函数，将基准函数取得最大值时的倾向度值作为社团发生融合的分 界线值。
[0093] 具体的，对表达式（11)的倾向度进行归一化可得表达式（12):
[0095] 将得到的对于、时间片的预测结果按照归一化后的倾向度降序排列，并与％时刻 的社团融合的真实情况进行对比来建立基准函数。对于每对被正确预测为将发生融合的社 团所对应的倾向度值TDd，进行如下计算：
[0098] 式中，1%为基于训练数据提取得到的发生融合的社团对所对应的倾向度值。进一 步地，根据表达式（13)建立基准函数，并将表达式（13)取得最大值时的T%的值作为判定 社团是否将会发生融合的分界线值diV(l。
[0100] 选取diV(l时希望选取的值对应a和0的值大小相对均衡，因此基准函数F值的 计算取a和0的调合平均数。
[0101] 在得到预测模型和判定社团是否将会发生融合的分界线值之后，便可以根据当前 时刻h的训练数据预测时间为tt时刻的社团的融合情况，具体包括：基于h时刻的训 练数据提取关键因素指标，以所得到的关键因素指标作为预测模型的输入数据代入表达式 (11)的预测模型，并将根据表达式（12)得到的归一化的预测结果
与社团融合 分界线值虹^进行比较以判断社团是否将发生融合。具体的，当
时，对 应的社团对的预测结果为将发生融合，反之则预测为不发生融合。
[0102] 根据本申请的实施例，基于预测到的将发生融合的社团对，可以进一步推出一个 具体的融合事件由哪几个社团构成。例如若预测社团i与社团j将发生融合，社团j与社 团k将发生融合，社团k与社团i将发生融合，那么社团i、j、k就构成了一个融合事件。通 过预测任意两个社团之间的融合行为，有效地缩小了观察范围，降低了大数据在进行社团 融合分析时的难度。
[0103] 举例而言，在上述对新浪微博进行预测的示例中，通过计算a、0及F，可以得到 使F取得最大值0.13时的TD。的值为0.1247,将0.1247作为判定社团是否将会发生融合 的分界线值。当通过预测模型得到的TcLw大于0. 1247时，对应的社团对的预测结果为将 发生融合，当Td_g/j、于等于0. 1247时，对应的社团对的预测结果为不发生融合。
[0104] 基于训练数据建立的预测模型对社团的融合行为进行预测的方法是一种有监督 的训练方法，同时实验数据表明，实现该功能的准确率和召回率是效果很好的，可以支撑相 关的实际应用，且为社团演化方面的进一步研宄提供了便利。
[0105] 当然，在通过监督训练判断任意两个社团是否将发生融合时，还可以使用现有的 预测模型进行训练和预测。在本申请的其他实施例中，采用SVM模 型进行预测，实施过程 为：先将基于训练数据得到的关键因素指标组成的向量代入SVM预测模型进行训练以确 定社团发生融合的分类器；再将基于距待预测的时间点最近的时间片的数据得到的关键 因素指标组成的向量代入所述SVM预测模型，并根据得到的分类预测结果判断社团是否 会发生融合。具体的，记At时间片社团(^和q之间的直接因素指标分别为内部结构
，间接因 素为社团的外部结构相似度
> 将这四个参数分别进行归一化处理，则该模块 所使用的第n条训练集输入变量为
[0107] 第n条训练集数据输出变量为
[0108] 进一步地，将所有的训练集输入、输出变量代入分类器中，可以训练得到分类模型 即超平面，然后代入归一化后的h时间片的预测输入数据，其中第n条预测输入数据输入 变量为
[0110] 将其带入分类模型中根据计算结果为+1或-1即可得知该数据在超平面的哪一 侦牝即其预测结果为，在△t时刻社团是否会融合。
[0111] 需要说明的是，在真实的社交网络中，社团未融合事件远远多于社团融合事件，因 此采集的到的初始训练集中未融合社团样本量远多于融合社团样本量。因此，采用本申请 实施例所建立的倾向度模型对于任意的关键因素指标值均可得到社团融合倾向度值，且得 到的社团融合倾向度值具有明显的区分度。而SVM模型的预测结果会倾向样本多的类，会 出现预测出的融合社团个数为零的情况。若对样本进行抽样以达到两类样本量均衡，则会 大大降低样本数据质量，得到的训练模型也会严重失真。
[0112] 另外，前面的预测方法都是直接对任意两个社团之间是否将会发生融合进行预测 的，但显然地，预测哪两个社团将发生融合，或是哪些社团将发生融合，都是基于社团自身 具有发生融合的可能性的基础之上的，因此，在本申请的另一个实施例中，通过先对单个社 团是否具有参与融合的可能性进行判断，进一步缩小预测的范围，如图5所示，该方法包 括：步骤S510、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据 作为训练数据；步骤S520、对训练数据进行静态社团和动态社团的划分；步骤S530、基于所 述静态社团和所述动态社团对每一个社团分别进行预测，得到将会参与融合的社团集合； 步骤S540、基于训练数据提取所述社团集合中任意两个社团之间的关键因素指标；步骤 S550、对所述关键因素指标进行监督训练，并根据监督训练的学习结果判断任意两个社团 是否会发生融合。
[0113] 具体地，在基于所述静态社团和所述动态社团对每一个社团分别进行预测的步骤 中，可以采用现有技术中的预测单个社团是否会参与融合的任何方法来实现。举例而言，采 用现有的SVM支持向量机的分类算法，对于时间片的各社团，提取三个基本指标：社 团大小、社团的内部边和社团节点度总和的比值（In-Degree)、以及社团在时间片tQ_At时 与在时间片h-2At时的Jaccard相似系数，及这三个指标的"一阶变化指标"和"二阶变 化指标"。观察这些社团在h时间片是否与其他社团发生融合事件（融合记为1，不融合记 为-1)。将以上指标和融合结果代入SVM分类器进行训练得到预测模型。同样，取h时间 片的社团的各指标，代入预测模型中，分类结果为"1"，则预测结果为该社团即将与其他社 团发生融合事件，相反若分类结果为"-1"，则预测结果为该社团不会与其他社团发生融合 事件。由此确定将会参与融合的社团的集合，这样在基于上述集合建立关键因素指标时，可 以极大地减少工作量，提高预测效率。
[0114] 本申请实施例的社团融合预测方法可以应用与有权网络的预测，具有更加普遍的 应用范围。通过定义任意两个社团之间的关键因素指标，实现对两个社团之间或多个社团 之间的融合行为的有效预测。
[0115] 虽然本发明所揭露的实施方式如上，但所述的内容只是为了便于理解本发明而采 用的实施方式，并非用以限定本发明。任何本发明所属技术领域内的技术人员，在不脱离本 发明所揭露的精神和范围的前提下，可以在实施的形式上及细节上作任何的修改与变化， 但本发明的专利保护范围，仍须以所附的权利要求书所界定的范围为准。
【主权项】
1. 一种社团融合事件的预测方法，包括： 步骤一、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据作 为训练数据； 步骤二、对训练数据进行静态社团和动态社团的划分； 步骤三、基于训练数据提取任意两个社团之间的关键因素指标； 步骤四、对所述关键因素指标进行监督训练，并根据监督训练的学习结果判断任意两 个社团是否会发生融合。2. 根据权利要求1所述的方法，其特征在于， 所述关键因素指标包括两个社团之间的内部结构指标、所述内部结构指标的一阶变化 指标、二阶变化指标以及两个社团的外部结构相似度指标。3. 根据权利要求2所述的方法，其特征在于，利用如下表达式提取所述两个社团之间 的内部结构指标：式中，Bd(i，j)为社团i与社团j之间的内部结构指标，Eu为社团i与社团j之间的 连接数，EjP L分别为社团i和社团j内部的连接数，N JP \分别为社团i和社团j内部 的节点数。4. 根据权利要求2所述的方法，其特征在于，利用如下表达式提取所述两个社团的外 部结构相似度指标：式中，Sim(i, j)为社团i与社团j的外部结构相似度指标；wi;k和w j，k分别表示社团i 和社团k之间以及社团j和社团k之间的权，其中，， Ej;k分别为社团i与社团k之间以及社团j与社团k之间的连接数，N 和Nk分别为社团 i、社团j与社团k内部的节点数;m为社团序号数。5. 根据权利要求2所述的方法，其特征在于，在所述步骤四中包括以下步骤： 利用基于训练数据得到的关键因素指标构建预测模型，并确定社团发生融合的分界线 值； 将基于距待预测的时间点最近的时间片的数据得到的关键因素指标代入所述预测模 型，并将得到的预测结果与所述分界线值进行比较以判断社团是否会发生融合。6. 根据权利要求5所述的方法，其特征在于，利用如下表达式构建所述预测模型：式中，以，,，为社团i与社团j之间发生融合事件的倾向度，为概率拟合函数，和 V分别为社团i与社团j之间的内部结构指标的一阶变化指标、二阶变化指标 以及外部结构相似度指标；tjP t ^ △ t分别表示不同的时间点，△ t为时间间隔。7. 根据权利要求5或6所述的方法，其特征在于，在确定社团发生融合的分界线值的步 骤中包括： 将根据所述预测模型预测得到的倾向度值进行归一化处理； 利用处理后的倾向度值与基于训练数据提取得到的社团融合情况建立基准函数； 将基准函数取得最大值时的倾向度值作为社团发生融合的分界线值。8. 根据权利要求7所述的方法，其特征在于，所述基准函数根据如下表达式建立：式中，F为基准函数，α和β为参数，TDtlS基于训练数据提取得到的发生融合的社团 对所对应的倾向度值。9. 根据权利要求1所述的方法，其特征在于，步骤四包括以下步骤： 将基于训练数据得到的关键因素指标组成的向量代入SVM预测模型进行训练以确定 社团发生融合的分类器； 将基于距待预测的时间点最近的时间片的数据得到的关键因素指标组成的向量代入 所述SVM预测模型，并根据得到的分类预测结果判断社团是否会发生融合。10. 根据权利要求1所述的方法，其特征在于，在步骤三之前还包括： 基于所述静态社团和所述动态社团对每一个社团分别进行预测，得到将会参与融合的 社团集合； 在步骤三中，基于训练数据提取所述社团集合中任意两个社团之间的关键因素指标。
【专利摘要】本发明公开了一种社团融合事件的预测方法，包括：步骤一、将网络原始数据按照设定的时间片进行分割，并从中选取多个时间片数据作为训练数据；步骤二、对训练数据进行静态社团和动态社团的划分；步骤三、基于训练数据提取任意两个社团之间的关键因素指标；步骤四、对所述关键因素指标进行监督训练，并根据监督训练的学习结果判断任意两个社团是否会发生融合。该方法实现了对任意两个社团或多个社团是否会发生融合事件的预测，预测可靠性高，可普适于绝大多数有权或无权的复杂网络的分析。
【IPC分类】G06K9/62, G06Q50/00, G06Q10/04
【公开号】CN104899657
【申请号】CN201510314273
【发明人】唐晓晟, 李巍, 胡铮, 张诗悦
【申请人】北京邮电大学
【公开日】2015年9月9日
【申请日】2015年6月9日
最新回复(0)