王 刚
(安康学院,陕西 安康 725000)
针对社区发现的研究是当前国内外研究的热点之一[1]。社会网络(social networks)是指社会中个人之间、组织之间或者个人与组织之间比较持久、稳定的社会关系模式,通常表示为节点的集合,同一社区节点集合之间的连接较多,如果节点集合之间连接较少,则认为属于不同的社区。研究网络中的社区有助于分析网络行为,对于个性化推荐具有重要的意义。
目前主要的社区发现算法有谱平分法[2-3]、KL算法、层次聚类法、GN算法等。谱平分法由于涉及到许多矩阵特征向量的计算,计算的时间复杂度可达O(n3),在大数据环境中,它的效率成为瓶颈。有研究人员从社会学角度研究了社区结构,研究了人际之间的信任关系及提取[4],对相似度计算方法进行改进[5-6],采取角色连接轮廓方法从结构上进行划分,发现它们属于外围串类型。也有研究人员利用社会网络个体间的关系类别和个体间对应社会属性相似度引入关系模型来进一步量化团队成员个体间的关系强度[7]。此外,还有学者对从朋友关系、距离变化等角度发现社区结构进行研究[8-9]。上述研究能在一定条件和背景下发现成员之间的关系和结构,这些算法注重于网络节点的信息,如出度、入度[10],而对社区结构的动态、不对称、模糊的特性考虑不够。通常认为,结构上临近的节点,应该属于一个社区,而且关系是对称的,即:如果a信任b,那么b就信任a。而实际应用中,考虑到一些具体的关系[11],上述结论不一定有效,如应用GN算法,可能会把边“a→b”作为两个社区的分界线,如果a和b本身属于事件非常重要的成员,把他们分割到两个社区就不合适。……