基于Normal矩阵谱平分算法的网络社团结构识别设计开题报告

1. 研究目的与意义（文献综述）

1)目的与意义

科技的发展，特别是计算机网络信息技术的突飞猛进使人类社会步入了网络的时代[1]。其实我们一直处于各式各样的复杂网络中，大自然的生态网络，动物个体的神经网络、新陈代谢网络，国家之间的政治、经济、关系网络，以及与人类日常生活密切相关的电力网络、交通运输网络。由此可见，人类时时刻刻都处在复杂网络的世界中。这些网络每时每刻都在影响着人类社会和人类生活，如:网络病毒在互联网传播，sars病毒，禽流感的扩散，城市交通网络的合理布局，经济危机的产生及对世界经济的影响，生命科学中蛋白质网络结构的研究等。这些因素决定了需要对各种自然和人工复杂网络进行认识和研究[2,3]。复杂网络之所以称之为复杂，不仅在于网络规模的巨大，节点多，一节点之问的边多导致的网络结构复杂，而且网络行为还具有复杂性，网络在时间、空间卜也都有动态的复杂性。

对复杂网络的研究起源于数学领域，著名的欧拉“七桥问题”是图论的研究开端，随机图理论的建立在数学上开创了对复杂网络的系统性研究的先例[4]。然而这些研究只是简单的、随机的、抽象的数学方法的研究。现实中网络并不完全是简单规则和随机的。直到20世纪末，对复杂网络的研究终于不再局限于数学领域，考虑到现实中的大量节点及复杂连接结构的实际网络，科学家从社会学到物理学等众多学科中掀起了复杂网络的研究热潮。这一时期两个重要研究的发现推动了复杂网络研究新纪元的到来:1998年watts和strogatz将随机性引入到规则网路中，建立了著名的小世界网络模型(ws小世界网络模型)，该模型真实的描述了实际网络存在的小世界特性[5]:1999年，barabasi和albert在对万维网的数据进行统计分析时，考虑到实际网络中网络规模的不断增长特性(节点数量的不断增加)与网络中新的节点倾向于优先连接度较大节点的两个性质，发现网络节点的度分布服从幂律分布并建立无标度网络模型(ba模型)[6]。

近年来随着计算机软硬件水平的发展，计算机运算和存储能力的提高，使得处理更大更复杂的网络中的数据成为可能，多学科的交叉为对比不同类型复杂网，络的共性与相异性提供了更广泛的研究基础，日前复杂网络的研究已经涉及到物理、生物、社会、计算机、数学、金融等诸多学科。这些学科涉及的研究对象有:基因调控网络[7];www网络[8];科学家合作网络[9,10]；internet网络[11]等等。

2. 研究的基本内容与方案

1)1）本设计研究的基本内容包括：

a)（a）基于normal矩阵的谱平分法

基于normal矩阵的谱平分法是揭示复杂网络中多级结构和复杂关系的有力工具。基于标准矩阵 n=k ^-1a。 其中k是一个对角矩阵，其对角线上的元素对应各个节点的度，而a则为网络的邻接矩阵。利用行标准化的转换可得。矩阵的最大特征值总是等于1。相应的特征向量称为平凡特征向量。对于一个社团结构比较明显的网络，假设社团数目为m，则矩阵n有m-1个非常接近1的特征值，其他的特征值都与1有明显的差距。而这m-1个特征值对应的特征向量有一个非常明显的特征结构：在这m-1个特征向量中，同一个社团内的节点对应的元素非常接近。因此，如果网络的社团结构比较明显，这些特征向量中的元素分布就呈明显的阶梯状；而且，阶梯的等级数就等于社团的数目m。因此，只要研究这m-1个特征向量中的任意一个即可。但是当网络的社团结构不是十分明显时，这m-1个特征向量就不会呈现十分明显的阶梯状，而是接近一条连续曲线。此时，需要比较若干不同特征向量中的相应元素，才可以获得网络的社团结构。

3. 研究计划与安排

1)思考问题（1-3周)

查阅相关文献资料，明确研究内容，了解研究所需的相关知识。完成毕业设计周记，从第1周写起。

2)完成开题报告（第3周）

4. 参考文献（12篇以上）

[1]汪小帆，李翔，陈关荣.复杂网络理论及其应用[m].北京:清华大学出版社，2006.

[2]barabasi a l. linked: the new science of networks [m]. massachusetts: persus publishing,2003,6(5):243-270.

[3]watts d j. the‘new’science of networks. annual review of sociology[j].annual review of sociology,2004，30:243~27.