基于局部近邻传播及用户特征的社区识别算法

提出一种将局部近邻传播和考虑用户特征的相似性测度相结合实现社交网络中的社区识别的算法。一方面,通过放松代表点约束条件及限制消息传播范围为节点的局部近邻,算法在降低时间和空间复杂度的同时保持较小的识别精度损失,从而能够适应社交网络挖掘需要;另一方面,通过将节点的拓扑相似度和特征相似度相结合来描述节点的综合相似度,使算法能够适应社交网络采样数据中用户关联信息不完整的情况。通过在人工数据集和真实数据集上的对比实验表明,所提方法不仅具有近似线性的时间复杂度及线性的空间复杂度,而且在网络中的节点关联边信息不完整时仍保持较好的识别精度。

Community detection algorithm based on local affinity propagation and user profile

An algorithm based on local affinity propagation and a new similarity measure concerning user profile is proposed. On one hand, by loosening the exemplar constraint and requiring the messages propagate around a node's neighbors, the algorithm achieves lower time and space complexity without too much lost in clustering accuracy, which makes it adaptable to the mining of large-scale social networks. On the other hand, by designing a hybrid similarity measure based on the topological similarity and the profile similarity of the nodes, the algorithm can effectively tackle the situation of the social networks data without complete user relation information. The experimental results on the artificial datasets and the real-world datasets demonstrate that the algorithm not only has near-linear time complexity and linear space complexity, but also retains high de-tecting accuracy when handling incomplete networks.