1.一种基于多标签传播的社交网络重叠社区发现方法,其特征在于,所述方法包括以下步骤:采集社交网络数据,构造出以社交网络用户为节点,用户关系为边的社交网络图;
将用户节点的相似度映射到边的权重,并计算出各个节点的相似度;
基于各个节点的相似度,构建出所述社交网络图所对应的加权网络;
遍历加权网络中的每个节点的标签,当源节点传播到目标节点时,如果目标节点具有与源节点相同的标签,那么该标签的权重采用第一更新公式更新,否则采用第二更新公式更新;
第一更新公式表示为:
labelDic(vj).label←labelDic(vj)+wij×labelWeight×(yi+1);
第二更新公式表示为:
labelDic(vj).label←wij×labelWeight×(yi+1)其中,labelDic(vj).label表示在标签字典中存储的节点vj的标签权重;wij表示节点vi和节点vj边权值,通过节点的相似度公式计算而得;labelWeight表示标签权重;yi表示节点vi的标准标签数,即节点vi的标签数x减去节点标签最小的数Min比上节点标签最大数Max减去节点标签最小的数Min,表示为 yi是一个(0,1)标准化后的数;
去除传播更新后标签权重小于预设阈值的标签,如果节点标签数小于或等于k,就将全部标签作为该节点的新标签,如果节点标签数大于k,则取每个节点的前k个标签作为该节点的新标签;
对每个标签的节点数进行计数,选择节点数最多的k个标签,按照节点数依次递减的顺序,分别将具有该标签的用户划分到一个区域中,从而依次划分出k个区域最终的重叠社区。
2.根据权利要求1所述的一种基于多标签传播的社交网络重叠社区发现方法,其特征在于,各个节点的相似度的计算公式包括:其中,Similarity(vi,vj)表示节点vi和节点vj的相似度;s为节点标签的个数,I(Tik+Tjk)表示指标函数,Tik表示节点vi的第k个标签属性值,Tjk表示节点vj的第k个标签属性值;
当Tik+Tjk等于2时I(Tik+Tjk)为1,其他为0。
3.根据权利要求1所述的一种基于多标签传播的社交网络重叠社区发现方法,其特征在于,在遍历加权网络中的每个节点的标签后,该标签权重按照α线性递减。
4.根据权利要求1所述的一种基于多标签传播的社交网络重叠社区发现方法,其特征在于,在遍历加权网络中的每个节点的标签后,该标签权重按照半衰期函数递减。
5.一种基于多标签传播的社交网络重叠社区发现装置,其用于实现如权利要求1~4任一所述的一种基于多标签传播的社交网络重叠社区发现方法,其特征在于,所述装置包括:采集模块,获取社交网络数据,包括社交用户和社交用户之间的关系;
社交网络模块,用于构造出以社交网络用户为节点,用户关系为边的社交网络图;
相似度计算模块,用于计算出各个节点之间的相似度;
加权网络模块,用于根据各个节点之间的相似度,构建出所述社交网络图所对应的加权网络;
传播模块,用于遍历加权网络中每个节点的标签,并采用第一更新公式或者第二更新公式更新标签权重;
确定模块,用于根据更新后的标签权重,选择出节点的新标签;
划分模块,对每个标签的节点数进行计数,选择节点数最多的k个标签作为最终的重叠社区。
6.根据权利要求5所述的一种基于多标签传播的社交网络重叠社区发现装置,其特征在于,所述传播模块包括传播单元、判断单元、第一更新单元和第二更新单元;所述传播单元用于遍历源节点到目的节点之间的标签;所述判断单元用于判断所述目的节点中是否存在源节点中的标签,若存在则指向第一更新单元,否则指向第二更新单元;所述第一更新单元根据第一更新公式更新标签的权重;所述第二更新单元根据第二更新公式更新标签的权重。
7.根据权利要求5或6所述的一种基于多标签传播的社交网络重叠社区发现装置,其特征在于,所述传播模块包括标签权重衰减单元,所述标签权重衰减单元用于在遍历每个节点的一个标签后,对该标签的权重进行衰减。
8.根据权利要求7所述的一种基于多标签传播的社交网络重叠社区发现装置,其特征在于,所采用的衰减方式包括线性衰减或半衰期函数衰减。