计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2012年
6期
2300-2304
,共5页
图聚类%社会关系网络%k-medoids算法%最短路径算法%参考节点嵌入
圖聚類%社會關繫網絡%k-medoids算法%最短路徑算法%參攷節點嵌入
도취류%사회관계망락%k-medoids산법%최단로경산법%삼고절점감입
为解决社会关系网络图中节点没有坐标值、不能采用传统的欧几里得距离和曼哈坦距离进行聚类的问题,提出采用最短路径算法,来衡量点与点之间的相异度.针对最短路径算法具有时间复杂度大的缺点,引入基于参考节点嵌入的最短距离估算思想来估算两点之间的近似距离.在此基础上,针对DBLP数据集构成的社会关系网络图进行聚类,使用基于划分的k-medoids算法,分别采用以上两种距离算法,比较其优劣.实验证明改进后的算法和最短路径算法中的Dijkstra 算法相比,距离误差率小,时间复杂度大大降低,在提高效率的同时,取得了同样好的聚类效果.
為解決社會關繫網絡圖中節點沒有坐標值、不能採用傳統的歐幾裏得距離和曼哈坦距離進行聚類的問題,提齣採用最短路徑算法,來衡量點與點之間的相異度.針對最短路徑算法具有時間複雜度大的缺點,引入基于參攷節點嵌入的最短距離估算思想來估算兩點之間的近似距離.在此基礎上,針對DBLP數據集構成的社會關繫網絡圖進行聚類,使用基于劃分的k-medoids算法,分彆採用以上兩種距離算法,比較其優劣.實驗證明改進後的算法和最短路徑算法中的Dijkstra 算法相比,距離誤差率小,時間複雜度大大降低,在提高效率的同時,取得瞭同樣好的聚類效果.
위해결사회관계망락도중절점몰유좌표치、불능채용전통적구궤리득거리화만합탄거리진행취류적문제,제출채용최단로경산법,래형량점여점지간적상이도.침대최단로경산법구유시간복잡도대적결점,인입기우삼고절점감입적최단거리고산사상래고산량점지간적근사거리.재차기출상,침대DBLP수거집구성적사회관계망락도진행취류,사용기우화분적k-medoids산법,분별채용이상량충거리산법,비교기우렬.실험증명개진후적산법화최단로경산법중적Dijkstra 산법상비,거리오차솔소,시간복잡도대대강저,재제고효솔적동시,취득료동양호적취류효과.
