复杂网络聚类分析及其应用研究
|
摘要
复杂网络的研究已经成为互联网、社会学、生物学等多个领域的一个基础课题。节点的聚集现象是很多复杂网络具有的一个特性,被称为簇、社团或群。语义复杂网络的聚集现象可以揭示网络中节点间语义的相似性,据此可以从少量节点的精确语义获得其他节点的潜在语义。
首先,语义复杂网络是一种加权的复杂网络,以往的研究主要是为发现非加权复杂网络的聚集现象,本文将研究一种加权复杂网络即语义复杂网络的聚集算法从而发掘节点间的语义关系。这种加权复杂网络是将用户检索的反馈转化为描述对象语义关系的复杂网络。为此提出一种基于语义核的凝聚型层次聚类算法CACNSC,发现不同粒度下语义的聚集现象。
然后,通过推荐少量对象由专家标注,或根据少量对象的已有的精确语义,再基于层次聚类过程中构建的语义关系树,实现其他对象的语义标注。对含有大量噪音的模拟反馈数据和Princeton Shape Benchmark的真实反馈信息的实验表明,所提方法在语义聚集和标注两个方面都取得了较好的效果。
最终,将本文提出的算法应用的实际的三维模型检索系统中,随着用户反馈信息的增加所构建的语义复杂网络节点间的语义会更加丰富,不但提高CACNSC算法结果的准确率,这样也可以使得语义更加准确,提高相关检索效率。
Complex networks has become the Internet, sociology, biology and other fields of a basic task. Aggregation node is a feature in many of complex networks, known as clusters or groups. The aggregation of complex networks can reveal many potential problems and also reflect the relationship between network nodes. Previous studies found that non-weighted aggregation of complex networks. This thesis will examine the complex network that is the weighted complex network aggregation semantics.
First, this thesis studies the weighted complex network cluster. This complex networks converts various feedbacks into the semantic complex network. The thesis proposes an agglomerative hierarchical clustering method based on semantic core, named CACNSC, to analyze the semantic accumulation under different granularities.
Second, the thesis shows a mechanism to recommend a few important multimedia objects for authority annotation and states the automatically annotation method using semantic information of limited multimedia objects. The proposed method is verified by the ideal feedbacks with high noise and the real feedbacks of Princeton Shape Benchmark. The method performs quite well not only in semantic clustering but also in annotation.
Finally, this thesis implements a three-dimensional model retrieval system. With the increase in user feedback, the semantics of nodes will be more abundant. This can make more precise semantics to improve the retrieval efficiency.
首先,语义复杂网络是一种加权的复杂网络,以往的研究主要是为发现非加权复杂网络的聚集现象,本文将研究一种加权复杂网络即语义复杂网络的聚集算法从而发掘节点间的语义关系。这种加权复杂网络是将用户检索的反馈转化为描述对象语义关系的复杂网络。为此提出一种基于语义核的凝聚型层次聚类算法CACNSC,发现不同粒度下语义的聚集现象。
然后,通过推荐少量对象由专家标注,或根据少量对象的已有的精确语义,再基于层次聚类过程中构建的语义关系树,实现其他对象的语义标注。对含有大量噪音的模拟反馈数据和Princeton Shape Benchmark的真实反馈信息的实验表明,所提方法在语义聚集和标注两个方面都取得了较好的效果。
最终,将本文提出的算法应用的实际的三维模型检索系统中,随着用户反馈信息的增加所构建的语义复杂网络节点间的语义会更加丰富,不但提高CACNSC算法结果的准确率,这样也可以使得语义更加准确,提高相关检索效率。
Complex networks has become the Internet, sociology, biology and other fields of a basic task. Aggregation node is a feature in many of complex networks, known as clusters or groups. The aggregation of complex networks can reveal many potential problems and also reflect the relationship between network nodes. Previous studies found that non-weighted aggregation of complex networks. This thesis will examine the complex network that is the weighted complex network aggregation semantics.
First, this thesis studies the weighted complex network cluster. This complex networks converts various feedbacks into the semantic complex network. The thesis proposes an agglomerative hierarchical clustering method based on semantic core, named CACNSC, to analyze the semantic accumulation under different granularities.
Second, the thesis shows a mechanism to recommend a few important multimedia objects for authority annotation and states the automatically annotation method using semantic information of limited multimedia objects. The proposed method is verified by the ideal feedbacks with high noise and the real feedbacks of Princeton Shape Benchmark. The method performs quite well not only in semantic clustering but also in annotation.
Finally, this thesis implements a three-dimensional model retrieval system. With the increase in user feedback, the semantics of nodes will be more abundant. This can make more precise semantics to improve the retrieval efficiency.
引文
[1]Watts D, S. Strogatz. Collective dynamics of'small-world' networks. Nature. 1998,393(6684):440-442P.
[2]Barabasi A, R. Albert. Emergence of scaling in random networks. Science.1999, 286(5439):509P.
[3]Clauset A, C Moore, M Newman. Hierarchical structure and the prediction of missing links in networks. Nature,2008,453(7191):98-101P.
[4]Adamic L. Power-law distribution of the world wide web. Science.2000,287(5461): 2115P.
[5]Albert R., H. Jeong, A. Barabasi. Error and attack tolerance of complex networks.. Nature.2000:378-382P.
[6]陈进才,何平,葛雄资.面向复杂网络存储系统的元胞自动机动力学分析方法.软件学报.2008,19(10)：2517-2526页.
[7]吕金虎,王红春,何克清.复杂动力网络及其在软件工程中的应用.计算机研究与发展.2008,45(012)：2052-2059P.
[8]刘兴武,徐志伟.交互复杂度——面向网络计算的复杂度指标.计算机研究与发展,2004,41(012)：2088-2094P.
[9]Girvan. M, M. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America. 2002,99(12):7821P.
[10]Palla G. Uncovering the overlapping community structure of complex networks in nature and society. Nature.2005,435(7043):814-818P.
[11]Palla, G. A. Barabasi, T. Vicsek. Quantifying social group evolution. Nature.2007. 446(7136):664-667P.
[12]Newman M. Coauthorship networks and patterns of scientific collaboration. Proceedings of the National Academy of Sciences of the United States of America.2004,101(Suppl 1):5200P.
[13]杨博,刘大有LIU Jiming金弟,马海宾.复杂网络聚类方法.软件学报.2009,20(1)： 54-66P.
[14]Liljeros F. The web of human sexual contacts. Nature.2001.411(6840):907-908P.
[15]Jiang W. Hidden annotation for image retrieval with long-term relevance feedback learning. Pattern recognition.2005.38(11):2007-2021P.
[16]Leifman G, R Meir, A. Tal. Semantic-oriented 3d shape retrieval using relevance feedback. The Visual Computer,2005.21(8):865-875P.
[17]He X, P Jhala. Regularized query classification using search click information. Pattern recognition.2008.41(7):2283-2288P.
[18]Funkhouser T. A search engine for 3D models. ACM transactions on Graphics.2003.22(1)83-105P.
[19]Philip Shilane, Patrick Min, Michael Kazhdan, Thomas Funkhouser. The princeton shape benchmark. Proceedings of the Shape Modeling International.2004:1-12P.
[20]Zachary W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research.1977.33(4):452-473P.
[21]Pothen A,H.Simon, K, Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Metrix Analysis and Applications.1990.11(3):. 430-452P.
[22]Newman M. Detecting community structure in networks. The European Physical Journal B-Condensed Matter and Complex Systems.2004.38(2):321-330 P.
[23]Xu J, H. Chen. Criminal network analysis and visualization. Communications of the ACM.2005.48(6):100-107P.
[24]Barrat A., M Barthelemy, A Vespignani. Modeling the evolution of weighted networks. Physical Review E.2004.70(6):66149P.
[25]IE A, T. ET. Statistical analysis of weighted networks. Discrete Dynamics in Nature and Society.2008.
[26]Newman M. Analysis of weighted networks. Physical Review E.2004.70(5): 56131-56140P.
[27]解,汪小帆.复杂网络的一种快速局部社团划分算法.计算机仿真.2007.24(011)：82-85页.
[28]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法.计算机应用研究.2009(006)：2041-2043P.
[29]赵鹏.一种基于加权复杂网络特征的K——eans聚类算法.计算机技术与发展.2007.17(009)：35-37页.
[30]刘婷,胡宝清.基于聚类分析的复杂网络中的社团探测.复杂系统与复杂性科学.2007.4(001)：28-35页.
[31]吴文涛,肖仰华,何震流,汪卫,余韬.基于权重信息挖掘社会网络中的隐含社团.计算机研究与发展.2009.46(2)：540-546页.
[32]田野,刘大有,杨博.复杂网络聚类算法在生物网络中的应用.计算机科学探索：330-337页.
[33]许丹,李翔,汪小帆.复杂网络病毒传播的局域控制研究.物理学报.2007.56(003)：1313-1317页.
[34]潘灶烽,汪小帆,李翔.可变聚类系数无标度网络上的谣言传播仿真研究.系统仿真学报.2006.18(008)：2346-2348页.
[35]唐杰.语义社会网络.中国计算机学会通信.2010.第6卷(第8期)：24-29页.
[36]Boccaletti S. Complex networks:Structure and dynamics. Physics reports.2006. 424(4-5):175-308P.
[37]Danon L. Comparing community structure identification. Journal of Statistical Mechanics. Theory and Experiment.2005:09008P.
[38]Newman M, M. Girvan. Finding and evaluating community structure in networks. Physical Review E.2004.69(2):26113P.
[39]Park, J, M Newman. Origin of degree correlations in the Internet and other networks. Physical Review E.2003.68(2):26112P.
[40]Radicchi F. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America.2004.101(9): 2658P.
[41]Yang B, J. Liu. Discovering global network communities based on local centralities. ACM Transactions on the Web (TWEB).2008.2(1):1-32P.
[42]Newman M. Modularity and community structure in networks. Proceedings of the National Academy of Sciences.2006.103(23):8577P.
[43]Smyth S. A spectral clustering approach to finding communities in graphs. Society for Industrial Mathematics.2005:274-258P.
[44]谢福鼎,张磊,嵇敏,黄丹.一种基于谱平分法的社团划分算法.计算机科 学.2009,36(011)：186-188P.
[45]Zhao R, W. Grosky. Negotiating the semantic gap:from feature maps to semantic landscapes. Pattern recognition.2002.35(3):593-600P.
[2]Barabasi A, R. Albert. Emergence of scaling in random networks. Science.1999, 286(5439):509P.
[3]Clauset A, C Moore, M Newman. Hierarchical structure and the prediction of missing links in networks. Nature,2008,453(7191):98-101P.
[4]Adamic L. Power-law distribution of the world wide web. Science.2000,287(5461): 2115P.
[5]Albert R., H. Jeong, A. Barabasi. Error and attack tolerance of complex networks.. Nature.2000:378-382P.
[6]陈进才,何平,葛雄资.面向复杂网络存储系统的元胞自动机动力学分析方法.软件学报.2008,19(10)：2517-2526页.
[7]吕金虎,王红春,何克清.复杂动力网络及其在软件工程中的应用.计算机研究与发展.2008,45(012)：2052-2059P.
[8]刘兴武,徐志伟.交互复杂度——面向网络计算的复杂度指标.计算机研究与发展,2004,41(012)：2088-2094P.
[9]Girvan. M, M. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America. 2002,99(12):7821P.
[10]Palla G. Uncovering the overlapping community structure of complex networks in nature and society. Nature.2005,435(7043):814-818P.
[11]Palla, G. A. Barabasi, T. Vicsek. Quantifying social group evolution. Nature.2007. 446(7136):664-667P.
[12]Newman M. Coauthorship networks and patterns of scientific collaboration. Proceedings of the National Academy of Sciences of the United States of America.2004,101(Suppl 1):5200P.
[13]杨博,刘大有LIU Jiming金弟,马海宾.复杂网络聚类方法.软件学报.2009,20(1)： 54-66P.
[14]Liljeros F. The web of human sexual contacts. Nature.2001.411(6840):907-908P.
[15]Jiang W. Hidden annotation for image retrieval with long-term relevance feedback learning. Pattern recognition.2005.38(11):2007-2021P.
[16]Leifman G, R Meir, A. Tal. Semantic-oriented 3d shape retrieval using relevance feedback. The Visual Computer,2005.21(8):865-875P.
[17]He X, P Jhala. Regularized query classification using search click information. Pattern recognition.2008.41(7):2283-2288P.
[18]Funkhouser T. A search engine for 3D models. ACM transactions on Graphics.2003.22(1)83-105P.
[19]Philip Shilane, Patrick Min, Michael Kazhdan, Thomas Funkhouser. The princeton shape benchmark. Proceedings of the Shape Modeling International.2004:1-12P.
[20]Zachary W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research.1977.33(4):452-473P.
[21]Pothen A,H.Simon, K, Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Metrix Analysis and Applications.1990.11(3):. 430-452P.
[22]Newman M. Detecting community structure in networks. The European Physical Journal B-Condensed Matter and Complex Systems.2004.38(2):321-330 P.
[23]Xu J, H. Chen. Criminal network analysis and visualization. Communications of the ACM.2005.48(6):100-107P.
[24]Barrat A., M Barthelemy, A Vespignani. Modeling the evolution of weighted networks. Physical Review E.2004.70(6):66149P.
[25]IE A, T. ET. Statistical analysis of weighted networks. Discrete Dynamics in Nature and Society.2008.
[26]Newman M. Analysis of weighted networks. Physical Review E.2004.70(5): 56131-56140P.
[27]解,汪小帆.复杂网络的一种快速局部社团划分算法.计算机仿真.2007.24(011)：82-85页.
[28]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法.计算机应用研究.2009(006)：2041-2043P.
[29]赵鹏.一种基于加权复杂网络特征的K——eans聚类算法.计算机技术与发展.2007.17(009)：35-37页.
[30]刘婷,胡宝清.基于聚类分析的复杂网络中的社团探测.复杂系统与复杂性科学.2007.4(001)：28-35页.
[31]吴文涛,肖仰华,何震流,汪卫,余韬.基于权重信息挖掘社会网络中的隐含社团.计算机研究与发展.2009.46(2)：540-546页.
[32]田野,刘大有,杨博.复杂网络聚类算法在生物网络中的应用.计算机科学探索：330-337页.
[33]许丹,李翔,汪小帆.复杂网络病毒传播的局域控制研究.物理学报.2007.56(003)：1313-1317页.
[34]潘灶烽,汪小帆,李翔.可变聚类系数无标度网络上的谣言传播仿真研究.系统仿真学报.2006.18(008)：2346-2348页.
[35]唐杰.语义社会网络.中国计算机学会通信.2010.第6卷(第8期)：24-29页.
[36]Boccaletti S. Complex networks:Structure and dynamics. Physics reports.2006. 424(4-5):175-308P.
[37]Danon L. Comparing community structure identification. Journal of Statistical Mechanics. Theory and Experiment.2005:09008P.
[38]Newman M, M. Girvan. Finding and evaluating community structure in networks. Physical Review E.2004.69(2):26113P.
[39]Park, J, M Newman. Origin of degree correlations in the Internet and other networks. Physical Review E.2003.68(2):26112P.
[40]Radicchi F. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America.2004.101(9): 2658P.
[41]Yang B, J. Liu. Discovering global network communities based on local centralities. ACM Transactions on the Web (TWEB).2008.2(1):1-32P.
[42]Newman M. Modularity and community structure in networks. Proceedings of the National Academy of Sciences.2006.103(23):8577P.
[43]Smyth S. A spectral clustering approach to finding communities in graphs. Society for Industrial Mathematics.2005:274-258P.
[44]谢福鼎,张磊,嵇敏,黄丹.一种基于谱平分法的社团划分算法.计算机科 学.2009,36(011)：186-188P.
[45]Zhao R, W. Grosky. Negotiating the semantic gap:from feature maps to semantic landscapes. Pattern recognition.2002.35(3):593-600P.