计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
8期
165-171
,共7页
图汇总%概念分层%多目标规划%层次凝聚
圖彙總%概唸分層%多目標規劃%層次凝聚
도회총%개념분층%다목표규화%층차응취
Graph summarization%Concept hierarchy%Multi-objective planning%Hierarchical agglomerative
将原始图中节点分配到多个分组并根据原始边来确立分组间关系,这样得到的图称作汇总图.汇总图的规模可以由用户设定,用户可以通过浏览小规模的汇总图来获得原始图的相关信息.K-SGS方法是一种新的基于节点概念分层的图汇总算法,它解决了传统K-SNAP算法的汇总图规模参数受限问题.为了解决该问题,算法引入了节点的属性值概念分层,从而增强了图汇总过程中节点分组的灵活性:不仅可以合并同值的节点,还可合并具有相似值的节点.除了关注汇总过程中边的信息损失外,K-SGS方法还关注节点的信息损失,它将图汇总问题建模成多目标规划问题,并通过分层序列法和基于分级的统一评价函数两种不同策略来解决该问题.算法上,提出了快速的层次聚类方法,使得每轮可以合并多个聚类,从而提高效率.经数据集上的实验表明,新算法能生产各种规模参数的汇总图,并具有较好的汇总质量.
將原始圖中節點分配到多箇分組併根據原始邊來確立分組間關繫,這樣得到的圖稱作彙總圖.彙總圖的規模可以由用戶設定,用戶可以通過瀏覽小規模的彙總圖來穫得原始圖的相關信息.K-SGS方法是一種新的基于節點概唸分層的圖彙總算法,它解決瞭傳統K-SNAP算法的彙總圖規模參數受限問題.為瞭解決該問題,算法引入瞭節點的屬性值概唸分層,從而增彊瞭圖彙總過程中節點分組的靈活性:不僅可以閤併同值的節點,還可閤併具有相似值的節點.除瞭關註彙總過程中邊的信息損失外,K-SGS方法還關註節點的信息損失,它將圖彙總問題建模成多目標規劃問題,併通過分層序列法和基于分級的統一評價函數兩種不同策略來解決該問題.算法上,提齣瞭快速的層次聚類方法,使得每輪可以閤併多箇聚類,從而提高效率.經數據集上的實驗錶明,新算法能生產各種規模參數的彙總圖,併具有較好的彙總質量.
장원시도중절점분배도다개분조병근거원시변래학립분조간관계,저양득도적도칭작회총도.회총도적규모가이유용호설정,용호가이통과류람소규모적회총도래획득원시도적상관신식.K-SGS방법시일충신적기우절점개념분층적도회총산법,타해결료전통K-SNAP산법적회총도규모삼수수한문제.위료해결해문제,산법인입료절점적속성치개념분층,종이증강료도회총과정중절점분조적령활성:불부가이합병동치적절점,환가합병구유상사치적절점.제료관주회총과정중변적신식손실외,K-SGS방법환관주절점적신식손실,타장도회총문제건모성다목표규화문제,병통과분층서렬법화기우분급적통일평개함수량충불동책략래해결해문제.산법상,제출료쾌속적층차취류방법,사득매륜가이합병다개취류,종이제고효솔.경수거집상적실험표명,신산법능생산각충규모삼수적회총도,병구유교호적회총질량.
