图聚类的算法及其在社会关系网络中的应用.PDF

第２９卷第２期　　　 计算机应用与软件 Ｖｏｌ２９Ｎｏ．２ ２０１２年２月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｆｅｂ．２０１２ 图聚类的算法及其在社会关系网络中的应用 温菊屏　钟　勇 （佛山科学技术学院信息与教育技术中心　广东佛山５２８０００） 摘　要　　研究图聚类的算法问题。在基于划分的图聚类中，重点比较点与点之间距离的计算方法及其对聚类结果的影响。由于 社会关系网络图中点没有坐标值，所以不能使用欧几里得距离和曼哈坦距离。使用ｋｍｅｄｏｉｄｓ聚类算法时，分别采用最短距离和随 机漫步距离算法，将ＤＢＬＰ数据集构成的社会关系网络图分类成各个子图，通过实验数据验证两种算法的优劣。实验证明最短距离 算法获得聚类效果更为理想，达到了较好的分类效果。 关键词　　图聚类　社会关系网络　ｋｍｅｄｏｉｄｓ　最短距离算法　随机漫步距离算法 中图分类号　ＴＰ３０１ 文献标识码　Ａ ＧＲＡＰＨＣＬＵＳＴＥＲＩＮＧＡＬＧＯＲＩＴＨＭＡＮＤＩＴＳＡＰＰＬＩＣＡＴＩＯＮＩＮＳＯＣＩＡＬＮＥＴＷＯＲＫ ＷｅｎＪｕｐｉｎｇ　ＺｈｏｎｇＹｏｎｇ （ＩｎｆｏｒｍａｔｉｏｎａｎｄＥｄｕｃａｔｉｏｎａｌＴｅｃｈｎｏｌｏｇｙＣｅｎｔｅｒ，ＦｏｓｈａｎＵｎｉｖｅｒｓｉｔｙ，Ｆｏｓｈａｎ５２８０００，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｓｔｕｄｙｔｈｅｇｒａｐｈｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．Ｉｎｐａｒｔｉｔｉｏｎｂａｓｅｄｇｒａｐｈｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ｗｅｐａｒｔｉｃｕｌａｒｌｙｅｖａｌｕａｔｅｔｗｏ ｄｉｆｆｅｒｅｎｔｄｉｓｔａｎｃｅｍｅａｓｕｒｅｓｂｅｔｗｅｅｎｖｅｒｔｉｃｅｓａｎｄｔｈｅｉｒｉｎｆｌｕｅｎｃｅｔｏｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔ．Ａｓｔｈｅｖｅｒｔｉｃｅｓｉｎｓｏｃｉａｌｎｅｔｗｏｒｋｇｒａｐｈｉｃｓｄｏｎｏｔｈａｖｅ ｃｏｏｒｄｉｎａｔｅｓ，ｔｒａｄｉｔｉｏｎａｌｄｉｓｔａｎｃｅｍｅａｓｕｒｅｓｌｉｋｅＥｕｃｌｉｄｅａｎｄｉｓｔａｎｃｅｏｒＭａｎｈａｔｔａｎｄｉｓｔａｎｃｅｃａｎｎｏｔｂｅｕｓｅｄ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｕｓｅｔｗｏｄｉｆｆｅｒｅｎｔ ｄｉｓｔａｎｃｅｍｅａｓｕｒｅｓｂａｓｅｄｏｎｓｈｏｒｔｅｓｔｐａｔｈｄｉｓｔａｎｃｅａｎｄｒａｎｄｏｍｗａｌｋｄｉｓｔａｎｃｅｒｅｓｐｅｃｔｉｖｅｌｙｗｈｅｎａｐｐｌｙｉｎｇｔｈｅｋｍｅｄｏｉｄｓｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ， ａｓｓｏｒｔｔｈｅｓｏｃｉａｌｎｅｔｗｏｒｋｇｒａｐｈｉｃｓｃｏｍｐｏｓｅｄｏｆＤＢＬＰｄａｔａｓｅｔｉｎｔｏｖａｒｉｏｕｓｓｕｂｇｒａｐｈｉｃｓ，ａｎｄａｔｔｅｓｔｔｈｅａｄｖａｎｔａｇｅａｎｄｄｉｓａｄｖａｎｔａｇｅｏｆｔｈｅｓｅｔｗｏ ａｌｇｏｒｉｔｈｍｓｗｉｔｈｅｘｐｅｒｉｍｅｎｔａｌｄａｔａ．Ｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｄｉｓｔａｎｃｅｈａｓｂｅｔｔｅｒｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｓａｎｄａｃｈｉｅｖｅｓ ａｃｃｅｐｔａｂｌｅｃｌａｓｓｉｆｉｃａｔｉｏｎｅｆｆｅｃｔ． Ｋｅｙｗｏｒｄｓ　　Ｇｒａｐｈｃｌｕｓｔｅｒｉｎｇ　Ｓｏｃｉａｌｎｅｔｗｏｒｋ　ｋｍｅｄｏｉｄｓ　Ｓｈｏｒｔｅｓｔｐａｔｈｄｉｓｔａｎｃｅ　Ｒａｎｄｏｍｗａｌｋｄｉｓｔａｎｃｅ 方法。社会网络指的是社会成员及其相互关系的集合，用表示 ０　引　言 各成员的节点和用表示成员之间的各种社会关系的边，构成图 结构，以此来描述社会网络。同时，社会关系可以表现为多种形 聚类是一个将数据集划分成若干簇或类的过程，使得同一类 式，如人与人之间的朋友关系、上下级关系、科研合作关系和文 内的数据对象具有较高的相似度，而不同类之间