《复杂网络理论及其应用》读书笔记 1引言 二十世纪，科学研究的特点是分析的方法，还原论的方法：物理学（牛顿力学、量子力学、电子论、半导体），化学（量子分子论），生物（双螺旋结构）；建筑工程（应力应变分析），……。 二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法。普列高津的耗散结构理论，哈肯的协同学，混沌和复杂系统理论，系统生物学……。 当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而整合的方法在于了解细部以后，研究“如何组合”的问题。这种方法导致复杂网络结构的研究。美国《Science》周刊：“如果对当前流行的、时髦的关键词进行一番分析，那么人们会发现，“系统”高居在排行榜上。” 2复杂网络的统计特征 如前所述，复杂网络具有很多与规则网络和随机网络不同的统计特征，其中最重要的是小世界效应（small -world effect）和无标度特性（scale -free property）。 在网络中，两点间的距离被定义为连接两点的最短路所包含的边的数目，把所有节点对的距离求平均，就得到了网络的平均距离（average distance ）。另外一个叫做簇系数（clustering coefficient）的参数，专门用来衡量网络节点聚类的情况。比如在朋友关系网中，
你朋友的朋友很可能也是你的朋友；你的两个朋友很可能彼此也是朋友。簇系数就是用来度量网络的这种性质的。用数学化的语言来说，对于某个节点，它的簇系数被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例，网络的簇系数C则是所有节点簇系数的平均值。研究表明，规则网络具有大的簇系数和大的平均距离，随机网络具有小的簇系数和小的平均距离。1998 年，Watts 和Strogatz 通过以某个很小的概率p 切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络（WS 网络），它同时具有大的簇系数和小的平均距离，因此既不能当作规则网络处理，也不能被看作是随机网络。随后，Newman 和Watts 给出了一种新的网络的构造方法，在他们的网络（NW 网络）中，原有的连边并不会被破坏，平均距离的缩短源于以一个很小的概率在原来的规则网络上添加新的连边。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应，具有这种效应的网络就是小世界网络（small-world networks）。 图 1 ：小世界网络拓扑结构示意图左边的网络是规则的，右边的网络是随机的，中间的网络是在规则网络上加上一点随机的因素而形成的小世界网络，它同时具有大的簇系数和小的平均距离。
基于标签传播和社区融合的复杂网络社区检测复杂网络是各类复杂系统的抽象形式,具有无标度性、小世界性、聚集性和度的幂律分布等性质。复杂网络中的社区结构是网络中内部连接较多,与外部连接较少的节点集合。复杂网络的社区检测就是根据其节点连接信息和网络拓扑结构将网络划分成若干子网络的过程,对复杂网络中社区结构的检测有助于理解网络演变过程并发掘网络 中潜在的信息。针对复杂网络社区检测的相关研究越来越多,进化算法,标签传播算法,社区融合策略等方法被不断提出并改进。然而以上算法目前还不够完善,存在着准确性低,检测随机,检测速度慢,易陷 入局部最优,模块度分辨率限制等问题。并且在网络信息量飞快增长的今天,复杂网络社区检测也逐渐趋向大数据化,针对大规模网络的 社区检测方法的研究变得尤为重要。本文设计了三种方法,对以上普遍存在的检测问题进行改进,主要工作如下:1)提出了一种基于循环 查找核节点的标签传播算法检测中小规模网络中的社区结构。首先循环查找核节点并根据相似度对网络进行预划分,降低小社区被吞并的可能,增加标签传播过程中传播方向的多样性;然后执行标签传播算法,对预划分后的网络进一步划分,降低标签传播算法本身的随机性;再根据节点与社区隶属度对划分结果进行修正,更准确的对网络进行划分。实验表明本算法在中小规模上的检测结果优于传统标签传播算法。2)提出了一种基于节点权值的标签传播策略对大规模现实网络进行社区检测。首先,根据节点度查找网络中影响力较大的核节点集合,核节点由于与其他节点连接较多,因此其传递和接受的信息量较大;
然后,根据节点与核节点集合中成员的相似度及节点度为网络中节点 赋权值,这样在标签传播过程中,影响力较大的节点标签将被优先选择,有效提高标签传播准确度;最后提出一个节点与社区的紧密度函数,并以此为目标函数对网络执行标签传播策略。这一函数将节点与 社区连接数和节点隶属邻居社区的程度结合,充分利用网络中的节点 及边的信息。实验表明本算法在大规模网络上可以获得很好的检测结果。3)提出了一种基于改进模块密度增量的大规模网络社区融合方法。首先,查找网络中局部核节点即潜在社区中心,将与核节点相似度值 高于给定阈值的邻居节点划分到核节点所在社区,将初步形成的社区 按外部连接数降序排序;提出一种基于模块密度的改进模块密度增量 作为目标函数,在社区合并过程中,优先考虑外部连接少的邻居社区 进行合并,避免错误融合;在局部社区融合过程中加入全局判断,同时 计算并比较每组可能融合的两个社区与各自邻居社区融合得到的改 进模块密度增量值,判断是否进行社区融合,进一步降低社区融合过 程中出现错误融合的概率。本算法解决了大多数社区融合算法基于模块度函数而导致的分辨率限制问题。实验结果表明,本算法对大规模 网络的检测与现有经典算法相比更优。
复杂网络研究概述 周涛柏文洁汪秉宏刘之景严钢 中国科学技术大学，近代物理系，安徽合肥：230026 摘要：近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网路的研究热潮。复杂网络区别于以前广泛研究的规则网络和随机网络最重要的统计特征是什么？物理学家研究复杂网络的终极问题是什么？物理过程以及相关的物理现象对拓扑结构是否敏感？物理学家进入这一研究领域的原因和意义何在？复杂网络研究领域将来可能会向着什么方向发展?本文将围绕上述问题，从整体上概述复杂网络的研究进展。 关键词：复杂网络小世界无标度拓扑性质 A short review of complex networks Zhou Tao Bai Wen-Jie Wang Bing-Hong? Liu Zhi-Jing Yan Gang Department of Modern Physics, University of Science and Technology of China, Hefei, 230026 Abstract: In recent years, the discoveries of small-world effect and scale-free property in real-life networks have attracted a lot of interest of physicists. Which are the most important statistical characteristics for complex networks that known from regular networks and random networks? What is the ultimate goal of the study of complex networks? Are physical processes sensitive to the topological structure of networks? What are the reason and meaning that physicist come into the research field on complex networks? What are the directions for future research? In the present paper, we concentrate on those questions above and give a general review about complex networks. Keyword: complex networks, small-world, scale-free, topological characters 1 引言 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[1]、社会关系网络[1,3-4]、交通网络[5]等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种新的构造网
—92— 大型复杂网络中的社区结构发现算法 胡 健1，董跃华1，杨炳儒2 (1. 江西理工大学信息工程学院，赣州 341000；2. 北京科技大学信息工程学院，北京 100083) 摘 要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现，引入边聚集系数的概念，提出基于边聚集系数的社区发现算法。将安然邮件数据集作为测试数据集，通过算法对比分析，证明该算法在时间复杂度上可以提高一个数量级。 关键词：边聚集系数；社区结构；社区发现 Community Structure Discovery Algorithm in Large and Complex Network HU Jian 1, DONG Yue-hua 1, YANG Bing-ru 2 (1. Faculty of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000; 2. School of Information Engineering, University of Science and Technology Beijing, Beijing 100083) 【Abstract 】The automatic search and community discovery in large and complex network has important practical applications. This paper applies the hypergraph based model and cluster algorithm in community structure discovery, introduces the concept of Edge Clustering Coefficient(ECC) to community structure discovery of simple graph and proposes an algorithm of community discovery based on ECC. Enron e-mail data sets are test data sets, through comparative analysis of algorithm, to prove that this algorithm can significantly improve the time complexity. 【Key words 】Edge Clustering Coefficient(EBB); community structure; community discovery 计 算 机 工 程Computer Engineering 第34卷 第19期 Vol.34 No.19 2008年10月 October 2008 ·网络与通信· 文章编号：1000—3428(2008)19—0092—02 文献标识码：A 中图分类号：TP301.6 1 概述 复杂网络中社区发现(community finding)的研究起源于 社会学的研究工作。能够在大型复杂网络中自动搜寻或发现“社区”具有重要的实际应用价值[1]，如社会网络中的社区可能代表的是根据兴趣或背景而形成的真实的社会团体，引文网络中的社区或许代表的是针对同一主题的相关论文，万维网中的社区或许就是讨论相关主题的若干网站，而生物化学网络或者电子电路网络中的社区可能就是某一类功能单元。发现这些网络中的社区有助于更有效地理解和开发这些网络。与社区发现相关的成熟理论包括图论以及模式识别。Wu 和Huberman 的研究成果[2]以及Newman 和Girvan 的研究成果[3]使得复杂网络中的社区发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中的一个重要研究方向。Newman 和Girvan 把社区发现问题定义为将网络节点划分成若干组，使得组内的节点之间连接比较稠密而不同组节点之间的连接则比较稀少。Newman 和Girvan 在其研究中提出了基于边介数(edge betweenness)概念的分割方法，尽管该方法计算量很大，但由于其性能优越而成为社区发现研究的重要参考模型。 对于一般简单图的社区发现，也可以称之为基于图的聚类，把具有相同或者相似属性的有共性的节点聚合到一起，形成一个个的聚类[2]。这方面的方法有很多，最常用的有G-N 算法、谱二分法和层次聚类法。 尽管人们对复杂网络的社区发现问题已进行了大量的研究，但是仍然存在一些目前无法解决的基本问题[4]，如社区的概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需要的计算量却很大；更为 关键的是，很多算法不是针对异构数据集。这说明复杂网络中社区发现的研究还远没有成为体系，还有很多工作待完善。 2 边的聚集系数定义 为了刻画描述一个网络，通常有这样几个角度，一个是这个网络中点与点之间的距离以及整个网络的平均距离；另一个是每个节点的度以及整个网络的平均的度；还一个就是节点之间聚集的情况，点的聚集系数这个概念是用来体现对于某个节点A 来讲，如果B 和C 都是A 的邻接点(朋友关系)，那么B 和C 两者之间也有邻接(朋友)的可能性。 定义1 某节点n 的聚集系数(node clustering coefficient) ()C n 如下定义： (1)假设某节点n 的度是k ，则该节点的这些邻居之间可能形成边的最大数是： ()(1)/2T n k k =? (2)()E n 表示图中这些邻居之间实际的边的个数，则 ()()/()C n E n T n = 定义2 一个网络的聚集系数为这个网络中节点的聚集系数的平均值。 如图1所示，节点1的度为5，所以与它相连接的5个顶点之间最多存在54/210×=条边；而实际上另外5个顶点相互之间存在6条边，所以节点1的聚集系数是6/100.6=。 基金项目：国家自然科学基金资助项目(60675030) 作者简介：胡 健(1967－)，男，副教授、博士，主研方向：数据挖掘，智能信息检索；董跃华，副教授；杨炳儒，教授、博士生导师 收稿日期：2008-08-01 E-mail ：euguenehu@https://www.doczj.com/doc/0517278875.html,
1.引言 图论过去被用来描述大量的实际现象, 但就在现在图论研究不论是从经验[1]–[6] 还是理论[7]–[9]的观点已经从二元转变到加权图。实际文献有很多鲁棒化的因素广泛应用于因特网流量，航空节点，国际贸易领域。尤其是，其已经证明加权图能够在有限大小截断[3, 10]上展示连接幂率分布P(K), ; (ii)一个连接权重P(w) 和已给定连接的节点P(W) [11, 12]总权重的偏态分布与(iii) 一个在权杖节点度和范围在1.3到1.5的θ[10, 13]的幂率关系本文, 我们提出一个简单的随机模型，该模型可以使描述加权网络的结构以及演变的数量和权重同比增长并可以解释上述规律。在设定中，我们扩展啦Barabási 和Albert (BA) 模式[14]来适应网络加权力学。这是stanley和他的合作者扩展理论框架来解释在复杂系统中放缩比例结构问题的[15]–[17]。 我们用网络上贸易流量的数据来检验我们的模型，而贸易流量是现实世界内在权重网络经典的例子。国际贸易流量过去使用一种叫做引力模型的方法来测算的，引力模型和两国的面积大小以及距离有关。然而该方法最大的局限是无法获取存在与双边合作中的矩阵中的分数为零的数。尽管这个问题已经在标准经济理论[19]中得到解决，图论还是自然而然得成为有这种特征的数据的解决办法 我们选择贸易流量（简称ITN）作为我们模型的测试背景基于一下考虑：一，是ITN已经被广泛研究啦[5, 6], [20]–[24], 而以前关于ITN的研究可以验证我们模型得出的结论。我们知道在ITN案例中链环权重结构呈现标准型，其增长呈现尾现象[24]。第二,，节点强度和度的关系在密集且广泛的贸易利润互相作用的经济学关于ITN文献中是相当重要的，而且也是解释贸易流量的关键[25]。第三，尽管是由于ITN的结构惯性，在2008年的全球金融危机导致的贸易流量的大幅波动还是引起啦广泛关注。我们的理论为解释节点的向心性和网络流的方差提供啦依据。本论文有如下结构：第二部分给出的模型是最重要的。而后在第三部分和第四部分我们用ITN的数据模拟验证我们的模型。最后，我们会总结一些结论并列出以后研究的内容。 6 广泛的利润由大量的贸易伙伴和产品出口k组成，然而集中利润代表每个国家的装货产品w. 2. 模型 Barabási 和Albert [14] 提出啦简单随机网络增长模型,它是基于现实世界观察得来的程式化事实的优先连接。 [7, 9]. The route we take here exploits the theoretical framework recently put forward by Stanley and co-authors [16] to deal with the growth dynamics of complex systems. We prove that our model is capable of accurately matching the structural properties that characterize a number of real-world weighted networks. We therefore propose a generalized version of the BA model to describe the dynamics and growth of weighted networks, by modeling them as a set of links of different weights occurring among nodes. In particular, we assume that the weight of links grows according to a geometric Brownian motion (also known as Gibrat’s law of proportionate effects [26]), so that the expected value of the growth rate of link weights is independent of their current level. The key sets of assumptions in the model are the following [14, 16, 27]: 1. The network begins at time t = 0 with N0 nodes, each with a self-loop. At each time step t = {1, . . . , M}, a new link among two nodes arises; thus the number of links (excluding self-loops that are used only for initialization) existing at time t is mt = t . We write Ki (t) for the number of links of node i at time t (node degree). To identify
网络社区划分方法及评价 【摘要】网络社区结构是社会网络最普遍和最重要的拓扑属性之一，其特点是，同一社区内的节点连接密集，不同社区间的节点连接稀疏。揭示网络社区结构对分析复杂网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义，在社会网、生物网和万维网中具有广泛应用。本文主要从网络社区划分的起源、常见的社区划分方法及社区评价准则等三个方面介绍网络社区划分研究的相关工作。 【关键词】复杂网络；网络社区；社区划分；社会网络分析；社区的评价；局部社区划分 0.引言 网络科学将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个具有复杂连接关系的网络。然而，近几年的实证研究表明，这些看似毫不相干的且形态各异的真实系统的拓扑抽象都具有某些共同的拓扑性质，如小世界与无标度特性等等。由于它们所表现出来的拓扑性质与随机网络、规则网络等有着天壤之别，且节点众多，因此被称为复杂网络。目前，复杂网络成为技术、生物乃至社会各类复杂系统的非常一般的抽象方法与描述骨架，相关研究成为重要的学科交叉研究前沿。 所谓社区(community)即指网络的内聚子图，其基本特征表现为子图内部链接丰富，不同子图之间连接相对稀少。 1.常见网络社区划分方法 1.1基于优化思想的算法 基于优化思想的算法将复杂网络社区划分转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的社区结构。比如K-L算法、谱平分法、随机游走(Random Walks)算法和派系过滤(CMP)算法等。这些算法的突出优点是速度比较快，效率显著。但是缺点也很突出，这一类算法都需要知道网络社区的数目，甚至KL算法还需要知道每个社区中各有多少节点，才能正确划分。这显然不适于网络未知社区的探索。 1.2社会网络分析方法 源于社会网络分析中寻找社区结构的传统算法，主要基于分级聚类思想，按照各个节点之间连接的相似性或者强度，把网络自然地划分为各个子群。其具体实现方式又有两种：其一是往网络中添加边，即凝聚方法(agglomerative method)；其二是又从网络中移除边，即分裂方法(divisive method)。凝聚方法的基本思想是基于网络中节点某种相似性分层进行聚类的。初始时，每个节点为一个社区，然
全面解读《网络安全法》(二)课程90分 一、单选 ( 共 4 小题，总分: 40 分) （正确）1. 开展信息安全等级保护工作是保护信息化发展、维护国家信息安全的（），是信息安全保障工作中国家意志的体现。 A.基本制度 B.基本策略 C.基本方法 D.根本保障 （正确）2. 《网络安全法》增加了网络运营者必须履行（）的内容。 A.网络安全保护义务 B.政府和社会公众的监督 C.社会责任 D.法律法规 （正确）3. 《网络安全法》规定，国家实行网络安全（）保护制度。 A.等级 B.标准 C.规范 D.技术 （正确）4. 《网络安全法》指出，采取监测、记录网络运行状态、网络安全事件的技术措施，并按照规定留存相关的网络日志不少于（）。
A.一年 B.五个月 C.六个月 D.十八个月 二、多选 ( 共 2 小题，总分: 20 分) 1. 《网络安全法》中关于网络信息安全的亮点体现在（）。 A.合法、正当、必要原则 B.明确原则和知情同意原则 C.明确公民个人信息的删除权和更正权制度 D.公民个人信息、隐私和商业秘密的保密制度 （正确）2. 为了明确关键信息基础设施安全保护的责任，《网络安全法》从（）两大层面，明确了对关键信息基础设施安全保护的法律义务与责任。 A.政府 B.国家 C.关键信息基础设施运营者 D.社会 （以下瞎选）三、判断 ( 共 4 小题，总分: 40 分) 1. 网络空间的竞争，归根结底是人才的竞争。 正确
错误 2. 省级以上人民政府有关部门在履行网络安全监督管理职责中，发现网络存在较大安全风险或者发生安全事件的，可以按照规定的权限和程序对该网络的运营者的法定代表人或者主要负责人进行约谈。 正确 错误 3. 近年来，个人信息保护方面的问题十分突出。 正确 错误 4. 2016年11月7日，《中华人民共和国网络安全法》已由中华人民共和国第十二届全国人民代表大会常务委员会第二十四次会议通过，将于2017年6月1日起施行。 正确 错误
全面解读《网络安全法》（二）课程的考试 90分 各题型提交答案说明： 1.单选题及判断题点击圆形按钮进行单项选择，多选题点击勾选框进行多项选择。 2.选择题和判断题:直接点击选项，系统将自动提交答案。 3.未完成考试误操作推出系统后，在考试时间段内可重新进入系统考试。 4.完成考试后点击提交答案按钮，考试结束，不可再次进入系统考试。 5.答题完成后，点击考试页面左侧“未答题”按钮，确认无未答题后再提交答案。 6.未提交答案的试卷在考试时间结束后将强制提交答案。 一、单选 ( 共 4 小题，总分: 40 分) 1. 《网络安全法》指出，采取监测、记录网络运行状态、网络安全事件的技术措施，并按照规 定留存相关的网络日志不少于（）。 A.一年 B.五个月 C.六个月 D.十八个月 2. 开展信息安全等级保护工作是保护信息化发展、维护国家信息安全的（），是信息安全保障 工作中国家意志的体现。 A.基本制度 B.基本策略 C.基本方法 D.根本保障 3. 《网络安全法》增加了网络运营者必须承担（）的内容。 A.网络安全保护义务 B.政府和社会公众的监督 C.社会责任 D.法律法规 4. 计算机网络最突出的优点是（）。
A.存储容量大 B.资源共享 C.运算速度快 D.运算准确率高 二、多选 ( 共 2 小题，总分: 20 分) 1. 《网络安全法》中关于网络信息安全的亮点体现在（）。 A.合法、正当、必要原则 B.明确原则和知情同意原则 C.明确公民个人信息的删除权和更正权制度 D.公民个人信息、隐私和商业秘密的保密制度 2. 为了明确关键信息基础设施安全保护的责任，《网络安全法》从（）两大层面，明确了对关键信息基础设施安全保护的法律义务与责任。 A.政府 B.国家 C.关键信息基础设施运营者 D.社会 三、判断 ( 共 4 小题，总分: 40 分) 1. 2016年11月7日，《中华人民共和国网络安全法》已由中华人民共和国第十二届全国人民代表大会常务委员会第二十四次会议通过，将于2017年6月1日起施行。 正确 错误 2. 网络空间的竞争，归根结底是人才的竞争。 正确 错误 3. 省级以上人民政府有关部门在履行网络安全监督管理职责中，发现网络存在较大安全风险或
复杂网络理论及其应用研究概述 刘涛 ，陈忠，余哲 （上海交通大学安泰管理学院，上海市华山路1954号287＃信箱，200030） liuzhang@https://www.doczj.com/doc/0517278875.html, 摘 要：本文从统计特性、结构模型和网络上的动力学行为三个层次简述复杂网络相关研究，并着重介绍了网络上的传播行为，认为它代表了复杂网络在社会经济系统中的重要应用。 关键词：复杂网络、小世界、无标度网络、疾病传播 1. 引言 结构决定功能是系统科学的基本观点[1]。如果我们将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个网络，例如神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络、计算机网络可以看作是计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络，类似的还有电力网络、社会关系网络、交通网络等等[2][3]。强调系统的结构并从结构角度分析系统的功能正是复杂网络的研究思路，所不同的是这些抽象出来的真实网络的拓扑结构性质不同于以前研究的网络，且节点众多，故称其为复杂网络（complex networks ）。近年来，大量关于复杂网络的文章发表在Science 、Nature 、PRL 、PNAS 等国际一流的刊物上，从一个侧面反映了复杂网络已经成为国际学术界一个新兴的研究热点。 复杂网络的研究可以简单概括为三方面密切相关却又依次深入的内容：通过实证方法度量网络的统计性质；构建相应的网络模型来理解这些统计性质何以如此；在已知网络结构特征及其形成规则的基础上，预测网络系统的行为[3]。 2. 复杂网络的统计性质 用网络的观点描述客观世界起源于1736年德国数学家Eular 解决哥尼斯堡七桥问题。复杂网络研究的不同之处在于首先从统计角度考察网络中大规模节点及其连接之间的性质，这些性质的不同意味着不同的网络内部结构，而网络内部结构的不同导致系统功能有所差异。所以，对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步，下面简述之。 2.1 平均路径长度（The average path length） 网络研究中，一般定义两节点间的距离为连接两者的最短路径的边的数目；网络的直径为任意两点间的最大距离；网络的平均路径长度则是所有节点对之间距离的平均值，它描述了网络中节点间的分离程度，即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多，称之为“小世界效应”l [2]。这一提法来源 资助项目：国家自然科学基金70401019，高等学校博士点科研基金2002048020。 作者简介： - 1 -
复杂网络社区发现若干问题研究 近年来,复杂网络逐渐成为信息科学、社会学、物理学、乃至生命科学等学科研究的热点。所谓复杂网络,是指将自然界中的各个实体抽象为网络中的节点,实体与实体之间的关系抽象为网络中的边。 这使得自然界中的很多系统都可以表示为复杂网络的形式,例如社会关系网、科学家合作网、通信网、互联网、人类疾病基因网等等。研究发现,复杂网络具有复杂的内部结构和多样的结构特征,其中,模块性(即社区结构)是复杂网络的 一个重要特征,它表现出网络中的节点具有聚集化的特性,即社区内部节点之间 连接稠密、社区之间的节点连接稀疏。 此外,社区结构在现实世界中往往是“重叠”的。复杂网络(重叠)社区结构的发现对于分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律以及预测复杂网络的行为具有十分重要的意义。 目前,研究者提出了众多网络(重叠)社区发现方法,并将之成功应用于现实 系统的分析中,然而社区发现方法存在的问题还有很多,如复杂网络社区发现问 题与聚类分析问题两者之间的关系还有待研究；网络社区发现算法尤其是重叠社区发现算法的精度和效率还有待提高；传统的划分评价函数模块化Q函数存在分辨率的限制等等。鉴于复杂网络社区发现问题与传统机器学习中的聚类分析问题都是对数据进行划分,并且机器学习中的聚类分析研究日趋成熟,本文结合机器 学习相关的技术和方法,改进并提出了若干发现网络(重叠)社区的算法,主要贡 献如下：(1)揭示了社区发现问题和聚类分析问题之间的区别和联系,利用聚类分析中定义的相似度概念对GN (Girvan and Newman)算法进行改进,给出了快速的SGN (GN based on similarity)算法。
第８卷第１期 复杂系统与复杂性科学ｖ０１．８Ｎｏ．１２０１１年３月ＣＯＭ呻ＬＥＸＳＹＳＴＥＭＳＡＮＤＣＯＭＰＬＥＸＩＴＹＳＣＩＥＮＣＥＭａｒ．２０１１文章编号：１６７２—３８１３（２０１１）０１一００５７—１４ 复杂网络的社区结构 程学旗，沈华伟 （中国科学院计算技术研究所，北京１００１９０） 摘要：社区结构作为真实复杂网络所普遍具有的一个重要拓扑特性，在最近１０ 内得到了广泛而深入的研究。回顾了近几年国内外社区结构研究的主要进展， 点介绍社区发现的研究历程和研究成果，并结合社会计算的背景展望了社区结研究的未来发展方向和潜在的应用价值。 关键词：社区结构；社区发现；模块度；社会计算 中图分类号：Ｎ９４文献标识码：Ａ ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｏｆＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ ＣＨＥＮＧＸｕｅ－ｑｉ，（ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔｉｎｇＴｅｃｈｎ０１０９ｙ，ＣｈｉｎｅｓｅＳＨＥＮＨｕａ—ｗｅｉ ＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅ巧ｉｎｇ１００１９０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓａｃｏｍｍｏｎａｎｄｉｍｐｏｒｔａｎｔｔｏｐｏｌｏｇｉｃａｌｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｒｅａｌｗｏｒｌｄｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ， ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｈａｓｂｅｅｎｅｘｔｅｎｓｉＶｅｌｙｓｔｕｄｉｅｄｉｎｔｈｅｌａｓｔｄｅｃａｄｅ． Ｔｈｉｓｐａｐｅｒｒｅｖｉｅｗｓｔｈｅｍａｉｎｐｒｏｇｒｅｓｓｅｓｉｎｔｈｅｓｃｉｅｎｔｉｆｉｃｒｅｓｅａｒｃｈ ｏｎｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ．Ｅｓｐｅｃｉａｌｌｙ，ｔｈｉｓｐａｐｅｒｄｅｓｃｒｉｂｅｓｔｈｅｄｅＶｅｌｏｐｍｅｎｔａｔｔｈｅｄｅｔｅｃｔｉｏｎｏｆｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｆｒｏｍｖａｒｉｏｕｓｄｉｓｃｉｐｌｉｎｅｓ． Ｆｉｎａｌｌｙ，ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｓｏｆｔｈｅｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅａｎｄｔｈｅｐｏｔｅｎｔｉａｌａｐｐｌｉｃａｔｉｏｎｓ ｉｎｓｏｃｉａＩｃｏｍｐｕｔｉｎｇ．Ｋｅｙｗｏｒｄｓ：ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ；ｍｏｄｕｌａｒｉｔｙ；ｓｏｃｉａｌｃｏｍｐｕｔｉｎｇ ０引言 真实世界中的许多复杂系统可以表示成图或网络，包括社会网络、信息网络、生物网络和技术网络等［１剖。经验分析表明，这些复杂网络可以自然地分成一些节点组，使同一个节点组内的两个节点之间比不同节点组的两个节点之间更倾向于有边相连，网络的这种拓扑特性被称为社区结构，相应地，每个节点组被称为一个社区‘６’。 社区结构刻画了网络中连边关系的局部聚集特性，也体现了网络中连边的分布不均匀性。进一步，网络中的社区通常由功能相近或性质相似的网络节点组成，因此，社区被认为有助于揭示网络结构和功能之间的关系。卜引。以万维网（ＷｏｒｌｄｗｉｄｅＷｅｂ）为例，通过超链接紧密关联的网页形成一个个的社区，同一个社区的网页具有相近的话题［３刮。社区结构的示例如图１所示。 收稿日期：２０１０一】Ｏ一２９ 墓金项目：国家自然科学基金（６０８７３２４５，６０９３３００５） 作者简介：程学旗（１９７ｌ一），男，研究员，博导，主要研究方向为网络科学、海量信息检索和数据挖掘、社会计算、分布式计算和网络模拟仿真。 年重构
《网络安全法》解读系列之三 —网络产品与安全服务商 这部分安全条款，规定了网络产品和安全服务提供者的安全义务、个人信息保护义务、网络关键设备和网络安全专用产品的安全认证和安全检测制度、网络安全服务活动规范。 这里要提醒我们的产品提供商和服务商同行们，以及同学们，要重视本法中规定的相关安全义务和法律责任，大家是做安全的，安全意识和守法意识一定要很好才行呀。 【第二十二条】网络产品、服务应当符合相关国家标准的强制性要求。网络产品、服务的提供者不得设置恶意程序；发现其网络产品、服务存在安全缺陷、漏洞等风险时，应当立即采取补救措施，按照规定及时告知用户并向有关主管部门报告。 网络产品、服务的提供者应当为其产品、服务持续提供安全维护；在规定或者当事人约定的期限内，不得终止提供安全维护。 网络产品、服务具有收集用户信息功能的，其提供者应当向用户明示并取得同意；涉及用户个人信息的，还应当遵守本法和有关法律、行政法规关于个人信息保护的规定。 解读：本条款规定了网络产品和服务商需要履行的义务之一；要符合国标的强制性要求，特别强调不得设置恶意程序，和执行双告知特别是要向有关主管部门报告，不得随意终止提供安全服务。这里还提出了对用户信息收集的相关要求，具体用户信息的含义，请参考前面的重要概念中的解释。 适用法律责任：【第六十条】、【第六十四条】 【第六十条】违反本法第二十二条第一款、第二款和第四十八条第一款规定，有下列行为之一的，由有关主管部门责令改正，给予警告；拒不改正或者导致危害网络安全等后果的，处五万元以上五十万元以下罚款，对直接负责的主管人员处一万元以上十万元以下罚款：（一）设置恶意程序的； （二）对其产品、服务存在的安全缺陷、漏洞等风险未立即采取补救措施，或者未按照规定及时告知用户并向有关主管部门报告的； （三）擅自终止为其产品、服务提供安全维护的。 【第六十四条】网络运营者、网络产品或者服务的提供者违反本法第二十二条第三款、第四十一条至第四十三条规定，侵害个人信息依法得到保护的权利的，由有关主管部门责令改正，可以根据情节单处或者并处警告、没收违法所得、处违法所得一倍以上十倍以下罚款，没有违法所得的，处一百万元以下罚款，对直接负责的主管人员和其他直接责任人员处一万元以上十万元以下罚款；情节严重的，并可以责令暂停相关业务、停业整顿、关闭网站、吊销相关业务许可证或者吊销营业执照。 违反本法第四十四条规定，窃取或者以其他非法方式获取、非法出售或者非法向他人提供个人信息，尚不构成犯罪的，由公安机关没收违法所得，并处违法所得一倍以上十倍以下罚款，没有违法所得的，处一百万元以下罚款。
第17卷第4期2009年10月 系统科学学报 JOURNAL OF SYSTEMS SCIENCE Vo1.17No.4 oct ，2009 复杂网络及其在国内研究进展的综述 刘建香 （华东理工大学商学院上海200237） 摘要：从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内关于复杂网络理论及其应用的研究现状从两方面进行综述：一是对国外复杂网络理论及应用研究的介绍，包括复杂网络理论研究进展的总体概括、复杂网络动力学行为以及基于复杂网络理论的应用研究介绍；二是国内根植于本土的复杂网络的研究，包括复杂网络的演化模型，复杂网络拓扑性质、动力学行为，以及复杂网络理论的应用研究等。并结合复杂网络的主要研究内容,对今后的研究重点进行了分析。 关键词：复杂网络；演化；拓扑；动力学行为中图分类号：N941 文献标识码：A 文章编号：1005-6408（2009）04-0031-07 收稿日期：2009-01-05 作者简介：刘建香（1974—），女，华东理工大学商学院讲师，研究方向：系统工程。E-mail ：jxliu@https://www.doczj.com/doc/0517278875.html, 0引言 系统是由相互作用和相互依赖的若干组成部分结合的具有特定功能的有机整体[1]。而网络是由节点和连线所组成的。如果用节点表示系统的各个组成部分即系统的元素，两节点之间的连线表示系统元素之间的相互作用，那么网络就为研究系统提供了一种新 的描述方式[2、3] 。复杂网络作为大量真实复杂系统的高度抽象[4、5]，近年来成为国际学术界一个新兴的研究热 点，随着复杂网络逐渐引起国内学术界的关注，国内已有学者开始这方面的研究，其中有学者对国外的研究进展情况给出了有价值的文献综述，而方锦清[6]也从局域小世界模型、含权网络与交通流驱动的机制、混合择优模型、动力学行为的同步与控制、广义的同步等方面对国内的研究进展进行了简要概括，但是到目前为止还没有系统介绍国内关于复杂网络理论及应用研究现状的综述文献。本文从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内研究现状进行综述，希望对国内关于复杂网络的研究起到进一步的推动作用。 1.复杂网络模型的发展演化 网络的一种最简单的情况就是规则网络 [7] ，它 是指系统各元素之间的关系可以用一些规则的结构来表示，也就是说网络中任意两个节点之间的联系遵循既定的规则。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。20世纪50年代末，Erdos 和Renyi 提出了一种完全随机的网络模型———随机网络（ER 随机网络），它指在由N 个节点构成的图中以概率p 随机连接任意两个节点而成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p 决定。或简单地说，在由N 个节点构成的图中，可以存在条边，从中随机连接M 条边所构成的网络就叫随机网络。如果选择M =p ，这两种构造随机网络模型的方法就可以联系起来。规则网络和随机网络是两种极端的情况，对于大量真实的网络系统而言，它们既不是规则网络也不是随机网络，而是介于两者之间。1998年，Watts 和Strogatz [8]提出了WS 网络模型，通过以概率p 切断规则网络中原始的边并选择新的端点重新连接 31--
复杂网络社区结构划分方法 已有 3661 次阅读2009-4-30 08:38|个人分类:科研笔记|系统分类:科研笔记|关键词:网络，系统，复杂网络，社区结构，聚类，划分方法 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区”或“组”构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏[1][2]。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站[3]；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元[4][5]。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。 在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法[6]、谱平分法[7][8]、随机游走算法[9]和派系过滤算法[10][11]等；第二类是层次聚类算法，比如基于相似度度量
的凝聚算法[2]和基于边介数度量的分裂算法[1][12][13]等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法[14]、基于信息论的算法[15]、基于PCA的算法[16]和最大化模块度[17]的算法[18-23]等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法[24]，且Bo Yang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC)[25]。 尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。 关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009长篇综述文章Community Detection in graphs by Santo Fortunato (arXiv:0906.0612) 参考文献 [1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. PNAS, 2001, 99(12): 7821-7826. [2] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.