一种同时基于节点属性以及结构关系相似度的聚类方法

摘要

本发明公开了同时基于节点属性以及结构关系相似度的聚类方法，首先，根据节点属性和拓扑结构关系提出了统一距离估算模型。然后，针对节点属性以及结构的权重设定问题，提出了权重自调整算法。接着，提出了基于链表的稀疏矩阵计算和存储优化方法以提高本聚类方法的性能。最后，不断变化的网络对聚类方法造成大量重复计算以及不能实时更新聚类结果的问题，提出了自适应的聚类方法。本发明解决了复杂网络统一模型和性能问题，以及避免了大量重复计算并且满足了实时获取聚类结果的要求，提高了本聚类方法的实际应用性。

主权项

1.一种同时基于节点属性以及结构关系相似度的聚类方法，其特征在于，包括以下步骤：（1）以社会化网络图中的每一个实体为基础创建一个普通节点，提取各个实体的属性信息创建属性节点，以各个实体之间的关系为基础创建结构关系，得到增广网络图；其中，属性节点包括属性类别和属性值；定义每个类别的属性节点的权重为ω₁，ω₂……，ω_m；定义结构关系的权重为ω₀；（2）根据步骤（1）得到的增广网络图中节点之间的相似性建立统一距离估算模型，包括如下步骤：（2.1）根据每个属性节点的权重以及结构关系的权重，得到普通节点V_i到普通节点V_j之间通过结构关系的转移概率所有的转移概率组成矩阵P_v；普通节点V_i和普通节点V_j分别代表任意两个不同的普通节点；（2.2）根据每个属性节点的权重以及结构关系的权重，得到普通节点V_i与属性值为k的属性节点U_k之间的转移概率所有的转移概率组成矩阵A；（2.3）根据每个属性节点与普通节点之间的关系，得到属性值为k的属性节点U_k与普通节点V_i的转移概率所有的转移概率组成矩阵B；（2.4）根据马尔科夫链模型，定义网络图中每一个节点到所有跟它连接的节点之间的转移概率之和为1；同时设置过滤度f＝1%，如果两个节点之间的转移概率低于过滤度f，则直接把两节点间转移概率设为0；（2.5）由所述的矩阵P_v、矩阵A和矩阵B，得到概率矩阵P；概率矩阵P为$\left[\begin{array}{cc}{P}_V& A\\ B& 0\end{array}\right],$其中0为零矩阵；（2.6）根据随机漫步模型由概率矩阵P得到节点间访问概率的相关性矩阵M¹，然后由相关性矩阵M¹得到稀疏矩阵R¹；其中R^l中每一个元素为相关性矩阵M¹中相应位置元素的倒数；（2.7）由所述的稀疏矩阵R¹得到每个节点的密度函数D_i；所述的节点包括普通节点和属性节点；（3）获得聚类集合，包括如下步骤：（3.1）输入一个带节点属性的社会化网络图、两节点之间随机访问的长度限制l、访问接受率c，参数δ以及待输出聚类的个数n；（3.2）初始化属性以及结构关系的权重ω₀=ω₁=……=ω_m=1.0；（3.3）按照密度函数D_i由大到小的顺序对所有节点进行排序，然后取前n个节点作为聚类中心；（3.4）把每个增广网络图中的节点分配到离自己最近的聚类中心的集群中；（3.5）根据重新投票机制选择新的聚类中心；（3.6）根据熵值分布更新属性权重，同时比较聚类中心是否发生改变，若聚类中心不发生改变，将得到的n个聚类集合作为最终结果输出；如发生改变，则回到步骤（3.3）。