1.一种错误累积敏感的增量式动态社区发现方法,其特征在于,包括以下步骤:根据给定的动态社交网络,预估第一个时间片后所有时间片的错误累积,计算所述动态社交网络的错误累积最佳阈值;
在第一个时间片,采用静态方法对初始时间片进行社区划分,获得动态社交网络的初始社区结构;
从第二个时间片开始直到结束,判断当前时间片的错误累积预估值是否超过错误累积最佳阈值,是,则重新进行社区划分,获得当前时间片社区结构;否,则动态更新增量节点的社区归属,获得当前时间片的社区结构。
2.根据权利要求1所述的动态社区发现方法,其特征在于,所述错误累积最佳阈值的计算方法包括:预估第一个时间片后每个时间片的错误累积;
针对预设的动态社交网络的错误累积阈值序列,基于每个时间片的错误累积,分别计算社区划分准确性和时间消耗的杠杆值LOCT;选取LOCT最大值对应的错误累积阈值,为动态社交网络的错误累积最佳阈值。
3.根据权利要求2所述的动态社区发现方法,其特征在于,所述错误累积的预估公式为: 其中,IEAt表示预估的当前时间片t的错误累积,t0为最近一次采用静态方法划分社区的时间片,ΔNi表示从t0开始的第i个时间片的增量节点个数,Ni表示所述第i个时间片的节点总数。
4.根据权利要求2所述的动态社区发现方法,其特征在于,所述杠杆值LOCT的计算公式为:
其中,t为当前时间片,T为总时间片数,CCt为
第t个时间片和最近一次采用静态方法重新划分社区结构的时间片之间的相关系数,freq为采用静态方法重新划分社区结构的次数,ratio为比例系数;
所述相关系数CCt的计算公式为:
其中,t为当前时间片,t0为最近一次采用静态
方法划分社区结构的时间片;Et代表第t个时间片的边集合, 表示t0时间片的边集合;IEAt表示预估的当前时间片t的错误累积,threshod为错误累积阈值;
所述比例系数ratio的计算公式为: 其中,ΔEi为i时间片的增量边数,Ei为i时间片的总边数。
5.根据权利要求1所述的动态社区发现方法,其特征在于,从第二个时间片开始直到结束,获得当前时间片的社区结构方法具体包括:
1)预估每个时间片的错误累积IEAt;
2)判断IEAt是否超过所述错误累积最佳阈值,否,则进入3);是,则进入4);
3)以前一个时间片的社区结构为基础,动态更新增量节点的社区归属,获得当前时间片的社区结构;
4)重新采用和第一个时间片相同的静态方法对当前时间片进行社区划分,获得当前时间片的社区结构。
6.一种应用权利要求1-5所述方法的错误累积敏感的增量式动态社区发现系统,其特征在于,包括:错误累积预估模块、错误累积最佳阈值计算模块、初始时间片社区划分模块和后续时间片社区划分模块;
所述错误累积预估模块,用于预估动态社交网络给定时间片的错误累积;
所述错误累积最佳阈值计算模块,用于根据所述错误累积预估模块输出的错误累积结果计算所述动态社交网络的错误累积最佳阈值;
所述初始时间片社区划分模块,用于采用静态方法划分动态社交网络的第一个时间片,获得动态社交网络的初始社区结构;
所述后续时间片社区划分模块,用于从第二个时间片开始直到结束,判断所述错误累积预估模块输出的当前时间片的错误累积是否超过所述错误累积最佳阈值计算模块输出的错误累积最佳阈值,是,则重新进行社区划分,获得当前时间片社区结构;否,则动态更新增量节点的社区归属,获得当前时间片的社区结构。
7.根据权利要求6所述的动态社区发现系统,其特征在于,所述错误累积预估模块采用的错误累积的预估函数为: 其中,IEAt表示预估的当前时间片t的错误累积,t0为最近一次采用静态方法划分社区结构的时间片,ΔNi表示从t0开始的第i个时间片的增量节点个数,Ni表示所述第i个时间片的节点总数。
8.根据权利要求6所述的动态社区发现系统,其特征在于,所述错误累积最佳阈值计算模块针对预设的动态社交网络的错误累积阈值序列,分别计算社区划分准确性和时间消耗的杠杆值LOCT;选取LOCT最大值对应的错误累积阈值,为动态社交网络的错误累积最佳阈值。
9.根据权利要求8所述的动态社区发现系统,其特征在于,所述错误累积最佳阈值计算模块中,杠杆值LOCT的计算公式为:其中,t为当前时间片,T为总时间片数,CCt为
t时间片和最近一次采用静态方法重新划分社区结构的时间片之间的相关系数,freq为采用静态方法重新划分社区结构的次数,ratio为比例系数;
所述相关系数CCt的计算公式为:
其中,t为当前时间片,t0为最近一次采用静态
方法划分社区结构的时间片;Et代表t时间片的边集合, 表示t0时间片的边集合;IEAt表示预估的当前时间片t的错误累积,threshod为错误累积阈值;
所述比例系数ratio的计算公式为: 其中,ΔEi为i时间片的增量边数,Ei为i时间片的总边数。
10.根据权利要求6所述的动态社区发现系统,其特征在于,后续时间片社区划分模块包括当前时间片社区划分策略选择单元和当前时间片社区划分单元;
所述当前时间片社区划分策略选择单元,用于选取社区划分的策略,包括:如果所述错误累积预估模块预估的当前时间片的错误累积没有超过所述错误累积最佳阈值计算模块计算的错误累积最佳阈值,则当前时间片的社区划分采用增量更新策略,即以前一个时间片的社区结构为基础,动态更新增量节点的社区归属,获得当前时间片的社区结构;否则,当前时间片的社区划分采用重新划分策略,即重新采用和第一个时间片相同的静态方法对当前时间片进行社区划分;
所述当前时间片社区划分单元,用于按照所述当前时间片社区划分策略选择单元选取的策略完成当前时间片的社区划分。