重叠社区

重叠社区（共3篇）

重叠社区 篇1

1 简 介

在现实世界中,各种对象的行为通常呈现出团体性的特点,在复杂网络研究中便表现为社区性。处于同一社区的对象往往具有较大的相关性。通过在复杂网络中识别这样的社区,可以发现对象之间潜在的各种关系,对于复杂网络的研究具有非常重要的意义。

社区发现近年来已取得了很大的发展,人们在研究中发现,很多情况下结点可能处于不同的社区。比如由于学科的交叉性,一篇文献就有可能处于不同的文献社区。这种社区即称为重叠社区。对于重叠社区的研究,最流行的当属Palla等人提出的CPM(Clique Percolation Method)。此方法中使用了由K个顶点构成的完全图的概念,并已被应用到带权图、有向图及二分图中。随后, Kumpula 等人提出了一种快速执行的CPM,称为SCP算法。由于前两种方法要求图中存在大量的完全图,而不适用于完全图较少的情况,于是又有Baumes等人的通过两个有效的启发式IS和RaRe来寻找局部最优簇的方法,之后他们又对IS和RaRe两个启发式进行了改进。Zhang等人和Nepusz等人分别提出结合谱映射、模糊聚类、质量函数和基于结点相似度的两种方法。区别于以上方法,Evans和Lambiotte提出将社区看作边的集合而不是结点的集合的方法。

通过对以上多种算法的研究发现,重叠社区发现方法与一般非重叠的社区发现方法是相互独立,不能互相套用的。于是Steve Gregory[1]提出一种基于结点分裂的方法,可以将重叠社区发现转化为非重叠的社区发现:首先根据某种规则将一些结点分别分裂成两个结点,然后使用非重叠社区发现算法进行社区的划分,此时由一个结点分裂成的两个结点就可能处于不同的社区,也即将原来的一个结点划分在了不同的社区。使用此方法具有以下优点:(1)算法具有灵活、适应性高的特点。由于非重叠社区发现算法发展较早,已有的研究成果丰富,其在复杂度等方面优势较为明显。通过将重叠社区转化为非重叠社区,可以直接套用合适的非重叠社区发现算法。(2)算法考虑时更多着眼于结点分裂,从而简化了工作量。

基于结点分裂的重叠社区发现方法的有效性和时间复杂度取决于结点的分裂过程,而结点是否分裂是由分裂系数决定的。文献[1]中采用了CONGA和CONGO算法来计算分裂系数,CONGA采用全局的方法,时间复杂度较高,为O(n3),对大型网络并不适用;CONGO的时间复杂度为O(nlogn),但其有效性取决于社区的直径h,仅适用于社区直径较小的网络,对于现实网络来说,社区的直径是未知的、变化的,所以CONGO并不适合处理现实的网络。于是本文选择采用一种局部的方法来计算分裂系数,可以在有效发现社区的同时降低结点分裂过程的时间复杂度。

2 局部重叠社区发现算法

定义1 无向图G={V,E },V为所有结点的集合,E为所有边的集合。

本文将重叠社区发现分为结点分裂和社区发现两个过程。由于准确、快速的结点分裂可以提高本重叠社区发现算法的有效性并使时间复杂度降低,而一个结点是否分裂以及如何分裂由分裂系数决定,于是在下面的内容中将重点介绍分裂系数的计算过程:首先介绍单个结点的分裂系数的计算方法,然后介绍一种局部的方法来完成对所有结点分裂系数的计算。

2.1 分裂系数

分裂系数的概念最初是由Steve Gregory在文献[2]中提出的。分裂系数越大,结点越应该被分裂。在文献[2]中,分裂系数被定义为:假设结点被分裂为两个新结点,经过这两个新结点的最短路径的数量。由此定义分析可知,分裂系数实际反映的是结点作为社区边界的可能性,因此是可以采用别的方法来定义的。

社区间边界的局部度量最常用的是Radicchi等人[3]提出的边聚集系数。边聚集系数越小,其作为社区边界的可能性越大。一条边的边聚集系数定义如下:

式中,中s${}_{i,j}^{(g)}$表示包含该边的所有可能的长度为g的环的数量,z${}_{i,j}^{(g)}$表示实际包含该边的长度为g的环的数量,i和j分别为该边的两个端点。文献[3]中作者通过实验证明,公式(1)中g取3或4都可以有效地反映结点作为社区边界的可能性。

由于分裂系数和边聚集系数均反映的是点或边作为社区边界的可能性,于是,可以用将结点分裂后形成的虚拟边的边聚集系数来定义该结点的分裂系数。如图1所示,结点是三角形的顶点,则结点分裂后形成的虚拟边通常处于四边形中(如图2中的虚线)。于是结点的分裂系数如下:

分裂系数是在假设结点分裂后进行计算的,那么就需要考虑结点的分裂方式。假设待分裂结点的度为d,则理论上该结点有2d-1种分裂方式,相应的,会产生2d-1个分裂系数。为了尽可能的反映结点作为边界的可能性,就需要采用使分裂系数最大的分裂方式。假设待分裂的结点为a,结点a分裂生成结点a1、a2,以及边Ea1,a2,在公式(2)中分母s${}_{i,j}^{(4)}$表示所有可能的包含边Ea1,a2的四边形数量,通过分析可知,即等于包含结点a的所有三角形的数量。对于每个结点,s${}_{i,j}^{(4)}$值是确定的。因此,该结点分裂系数的大小实际取决于分子z${}_{i,j}^{(4)}$值。z${}_{i,j}^{(4)}$表示结点分裂后实际形成的四边形数量,其值会因分裂方式的不同而不同。根据公式(2),要使分裂系数最大,则需使z${}_{i,j}^{(4)}$值最小。此问题可以转化为:将结点a的所有邻居结点划分成两个集合,并使得两个集合间的连接数最小。为了简化计算过程,本文采用的集合划分步骤如下:(1)将a及其邻居结点构成子图,并在子图中计算所有边的边聚集系数,如图3即为图1中结点a执行这一步骤后的结果;(2)将子图中结点a及以a为端点的边删除,得到图4;(3)将具有最大边聚集系数的边的两个端点u和w合并为uw,若同时存在边Ex,u和Ex,w,则将它们替换为Ex,uw,并使Ex,uw的边聚集系数为Ex,u和Ex,w边聚集系数之和。(4)设结点a的度为d,重复步骤(3)d-2次。图5到图8为图4迭代执行步骤3的结果。由于结点a的度为6,所以迭代4次即可结束。通过以上步骤获得的两个集合之间的连接数即为z${}_{i,j}^{(4)}$值,如图8所示,结点a分裂系数计算公式中的z${}_{i,j}^{(4)}$值即为两个集合bcd和efg之间的连接数1。跟CONGA算法类似,本文采用以上方法获得的两个集合的连接数为最小或者接近最小。此时,结点的分裂方式即为:连接生成的两个结点,并使它们分别与以上两个集合中的结点相连,结点a的分裂方式如图2所示。

根据以上过程,公式(2)可以由公式(3)来代替:

其中Numtriangle表示以待分裂结点作为顶点的三角形数量,Numlink表示假设结点分裂形成的两个集合之间的最少连接数。

根据公式(3)可以计算出每个结点的分裂系数。需要注意的是,此时结点并没有真正被分裂。只有当分裂系数满足一定条件时,才保存之前的分裂方式。否则,结点不分裂。

2.2 重叠社区发现算法

本文采用一种局部的方法来计算所有结点的分裂系数。社区发现中的局部方法是指一种基于种子结点的方法。在图中随机选择s作为种子结点,局部的方法会在s的周围形成一个社区Cs,然后基于Cs进行“全局”的社区发现。通过反复的随即选择未分配的结点来应用以上方法,直到所有结点都已被分配。使用局部方法计算结点的分裂系数,可以保证所有结点的分裂系数只计算一遍,从而加快了结点分裂过程的运算速度。

考虑到实际情况,当结点的度小于4时,该结点并不适合作为重叠社区的边界,于是在结点分裂过程中,只有度大于等于4的结点才需要计算分裂系数。

本重叠社区发现算法在结点分裂之后采用经典的GN[4]算法进行社区发现,结合局部的计算结点分裂系数的过程,整个算法步骤如下:

(1) 将图中所有结点标注为“未操作”;

(2) 随即选择一个结点s作为种子结点,并保存s的所有邻居结点;

(3) 将s重新标注为“已操作”,当s的度不小于4时,用公式(3)来计算点s的分裂系数,若计算出的分裂系数大于给定阈值时,分裂结点s,并保存分裂后结点与源结点之间的对应关系;

(4) 对s所有的邻居结点中标注为“未操作”的结点重复(2)、(3)步操作;

(5) 重复以上过程直到所有结点都被标注为“已操作”;

(6) 使用GN算法对新生成的图进行社区发现;

(7) 将分裂后生成的结点还原为源结点。

执行第(1)步到第(5)步的结点分裂过程之后,会产生一个新的图G′,新图G′中分裂后的结点代替了G中的源结点。经过第(6)步执行GN算法,就可能出现分裂后结点处于不同社区的情况,通过第(7)步将它们还原为源结点,则源结点处于不同社区,这样便发现了重叠社区。

在计算结点分裂系数时假设结点以使分裂系数最大的方式进行分裂,这样保证了各个结点的分裂系数可以最大程度地反映其作为社区边界的可能性,然而此时结点并没有真正被分裂,只有其分裂系数满足一定条件时才需要进行分裂。本算法通过给定阈值的方式,当结点分裂系数大于阈值时分裂结点(第(3)步)。这样便可以在只计算一遍分裂系数的情况下保证结点分裂的有效性。分裂系数的阈值并没有标准的计算方法,可以采用最简单的方式:为了减小计算量,选择图的一个子图,计算子图中边的边聚集系数。根据已有的边聚集系数的数据手动选择一个合适的值作为分裂系数的阈值。

在本算法中,对于有n个结点m条边的图,假设所有结点的度均为d,所有结点是否被分裂仅需计算一遍,所以结点分裂过程的时间复杂度为O(nd),若取d=2m/n,时间复杂度为O(m),在稀疏图中,则为O(n),很显然,比全局的CONGA算法要快得多。

本算法的不足之处,在于由于采用了边聚集系数来计算结点的分裂系数,所以仅适用于三角关系较多的网络。然而这种类型的网络数量众多,故本算法还是具有很大应用空间的。

3 重叠社区发现实验及结果分析

本文采用的数据源为Mark Newman提供的Network data数据源,Newman主要提供了16个数据集,各数据集形成的图规模种类各不相同。于是可以选择多个数据集进行实验,以便得到更有效、更准确的结果。本文使用基于java的Prefuse包作为可视化工具。

图9为使用科学家的合著网络数据源(105个结点,441条边)进行实验后形成的社区结果。由图可知,共发现5个社区,而红色显示的结点即为同时处于不同社区的结点。

Nicosia在文献[5]中提出一种适合于重叠社区的模块度量Qov,跟模块度Q值类似,Qov越大,社区结构越好。在本文实验中,Qov用公式(4)来计算。

式中,m为图中所有的边数,δ(ci,cj,c)只有当结点i与结点j所属的社区都为c时为1,否则为0。Aij只有当结点i与结点j属于同一社区时为1,否则为0。k${}_i^{out}$为结点i与社区c外的结点相连的边数,k${}_j^{in}$为结点j与社区c内结点相连的边数。

β${}_{l(i,j),c}^{out}$$=\frac{{\displaystyle {\sum }_{\text{j}\in \text{V}}m}ax(\text{α}{}_{\text{i}},\text{α}{}_{\text{j}})}{|\text{V}|}$,αi=1/c,c为结点i所处的社区数量。

β${}_{l(i,j),c}^{in}$$=\frac{{\displaystyle {\sum }_{\text{i}\in \text{V}}m}ax(\text{α}{}_{\text{i}},\text{α}{}_{\text{j}})}{|\text{V}|}$,αi=1/c,c为结点i所处的社区数量。

图10中显示了分别采用本文算法和CONGA算法时以上社区发现结果的Qov值。由图可以看出,本文提出的算法在时间复杂度提高的情况下,跟全局的CONGA方法一样均是有效的。

4 结 语

本文将重叠社区发现分为了结点分裂和社区划分两个过程。首先采用局部的方法,使用改进的边聚集系数作为结点的分裂系数,分裂具有较大分裂系数的结点。然后使用非重叠社区发现方法进行社区发现。由于在计算分裂系数的过程中,所有结点的分裂系数只需要计算一遍,无需重复计算,从而降低了时间复杂度,同时通过实验证明了本算法的有效性。

摘要：研究重叠社区发现技术,可以将重叠社区转化为非重叠的社区发现。通过分裂结点后,使用已有的非重叠社区发现算法来进行社区划分,然后将分裂后的结点还原为源结点即可发现重叠社区。而结点是否分裂由分裂系数来衡量。使用局部的方法来计算结点的分裂系数,并分裂具有较大分裂系数的结点。实验表明此方法可以有效地发现重叠社区,并从时间复杂度上优于基于全局的方法。

关键词：重叠社区,边聚集系数,分裂系数,局部方法

参考文献

[1] Gregory S. Finding overlapping communities using disjoint community detection algorithms[M].in: S. Fortunato, R. Menezes, G. Mangioni, V.Nicosia(Eds.), Complex Networks, in: Studies on Computational Intelligence, vol. 207, Springer, Berlin, Germany, 2009:47-62.

[2]Gregory S.An Algorithm to Find Overlapping Community Structure inNetworks[C]//PKDD 2007.LNAI,vol.470,2Springer,Heidel-berg.2007:91-102.

[3] Radicchi F, Castellano C,Cecconi F, et al. Defining and identifying communities in networks[C]//Proceedings of the National Academy of Science of the United States of America, volume 101, March 2004:2658-2663.

[4]Newman M E J,Girvan M.Finding and evaluating community struc-ture in networks[J].Phys.Rev.E 69(2)(2004)026113.

[5]Nicosia V,Mangioni G,Carchiolo V,et al.Extending Modularity Def-inition for Directed Graphs with Overlapping Communities[J].EprintarXiv:0801.1647v3 at arxiv.org(2008).

重叠社区 篇2

1 对象与方法

1.1 病例入选条件及分组

(1) 2005年1月～2008年1月在我院住院接受冠脉造影和支架的患者。造影发现冠状动脉狭窄,病变长,需要植入2个及以上支架者。(2)患者随机分为国产支架Partner组与美国强生Cypher支架组。部分多支病变患者因费用原因转入Partner组。Partner支架为北京乐普医疗器械有限公司生产;Cypher为Cordis/Johnson&Johnson公司生产。

1.2 抗凝治疗及造影复查

(1)两组均顿服阿司匹林300mg和氯吡格雷300mg (择期患者术前24小时顿服,急诊PCI者术前顿服),PCI术后每天氯吡格雷75mg,阿司匹林300mgx1月、200mgx1月、之后100mg长期应用。(2)应用GE Advantx LCV+血管造影机进行冠状动脉造影和介入治疗,采集速度25帧/s,思创图像处理工作站进行图像处理。

1.3 观察临床事件及随访

(1)心肌梗死、冠状动脉旁路移植术(CABG)、再次PCI、支架再狭窄、心源性死亡、总死亡等。(2)出院后每月门诊随访,有症状者入院治疗。

1.4 统计学方法

临床试验资料经复核后输入电脑,所有数据均采用SPSS13.0软件包进行统计分析,计量资料以均数±标准差()表示;计数资料以百分比表示,采用独立t检验或x2检验,P<0.05为差异有统计学意义。

2 结果

2.1 入选患者基本情况

128例患者139处靶病变接受了重叠Partner支架;104例患者109处靶病变接受重叠Cypher支架作为对照组,两组介入的即刻成功率100%,术中对靶病变进行低压力(<8atm)预扩张,支架完全覆盖靶病变,支架重叠3～5mmm,对重叠处高压后扩张,两组支架在推送、定位、释放等方面无差异。基线情况见表1。

*P<0.05

两组患者在年龄、性别、高血压、糖尿病、心肌梗死、支架长度、重叠支架数等方面无统计学差异。Partner组高脂血症、三支病变患者的比例高,有统计学差异。

2.2 随访情况

所有病例随访1～2年,情况见表2,3。在冠脉长病变中重叠应用国产Partner支架临床效果与Cypher支架相近,具有较好的安全性。

*住院期间发生急性ST段抬高心肌梗死,药物保守治疗后出院;**非PCIS靶血管的搭桥

#住第二年时Partneir组和Cypher组分别有3例及2例建议行冠状动脉旁路移植术,患者拒绝;*造影证实支架再狭窄,再狭窄部位以支架两端常见

3 讨论

心在心血管介入临床工作中,处理冠脉血管长节段或弥漫性病变,需要2个及以上支架重叠应用,目前认为重叠应用药物洗脱支架,支架血栓和支架再狭窄风险增加,国外对Cypher、Taxus药物洗脱支架的重叠应用已积累了一些资料[1],有关国产药物洗脱支架重叠应用的资料较少,本研究通过以Cypher支架为对照,观察重叠国产Par tner支架的临床效果。

处理冠脉血管长节段或弥漫性等病变时,重叠应用药物洗脱支架的做法较为普遍,在临床中经常会应用美国强生公司的Cypher支架和我国乐普公司生产的Partner支架,两者均为雷帕霉素涂层支架,所以它们的作用机理相同,本研究表明Partner和Cypher两组支架在术中的操作性、手术结束时的即刻效果相似,在1～2年后期随访中,新发心肌梗死、再次血运重建以及死亡等情况也无明显差异,1年时两组均无死亡病例[2,3]。

部分多支病变患者因费用原因转入Partner组,但两组严重心脏不良事件(包括死亡、新发心肌梗死和再次血运重建)发生率无显著性差异,提示国产Partner支架有很好的安全性,在复杂长病变中的临床效果与Cypher支架相似[4]。

有人认为支架重叠处存在较高再狭窄风险,与支架重叠处局部抑制内皮细胞增生药物浓度高,金属负荷大,炎性物质渗出有关,而且也被动物模型病理所证实[5,6,7];而我们造影复查发现支架再狭窄部位以支架两端常见,与上述观点不符,可能与术中我们对重叠处进行了充分的后扩张,支架重叠处贴壁更好,而对支架的两端产生了不良影响,使支架两端再狭窄机率增加。

在第二年随访中两组药物支架的再狭窄,冠脉血管再次接受PCI的比例明显增加,提示药物洗脱支架可能存在“后期追赶现象”[8],这可能与药物洗脱支架周围存在长期慢性炎症,刺激增殖、炎性渗出有关;

本试验还存在某些局限,造影复查比例低,未能计算支架内晚期管腔丢失等数据,以提供更详尽的量化对比。

摘要：目的:对比研究重叠国产Partner与Cypher药物洗脱支架治疗冠状动脉长病变的疗效。方法:自2005年1月至2008年1月,128例患者接受了重叠国产Partner支架,104例患者接受重叠Cypher支架作为对照组。比较两组临床事件发生情况。结果:两组在1年、2年的主要临床事件无显著差异。结论:重叠国产Partner雷帕霉素药物洗脱支架与重叠Cypher支架的临床疗效相同,临床效果好,可治疗冠状动脉长病变。

关键词：冠脉长病变,重叠药物洗脱支架,国产Partner雷帕霉素涂层支架

参考文献

[1] Eleftheria Tsagalou, Alaide Chieffo,Ioannis lakovou,et al. Multiple Overlapping Drug-Eluting Stants to Treat Diffuse Disease of the Left Anterior Descending Coronary Artery.J Am Cull Cardiol, 2005; 45:1570～1573

[2] 胡健,张建盛,张奇,等.重叠药物洗脱支架术治疗冠状动脉长病变的临床疗效.介入放射学杂志,2006;15(2) :67～69

[3] 陈纪林,高润霖,杨跃进,等.雷帕霉素药物洗脱支架在冠心病复杂病变中应用的近、远期疗效.中华心血管病杂志,2004;32:867～869

[4] 杨锋,李绍龙,李易,等国产长药物支架治疗冠脉长病变的疗效评估 中国心血管病研究杂志 2007 5(4) :282～283

[5] Aloke V Finn,Gaku Nakazawa,Michael Joner,et al.Vascular Responses to Drug Eluting Stents: Importance of Delayed Healing. Arterioscler.Thromb.Vasc.Biol. □ 2007;27:1500～1510

[6] Aloke V.Finn, Frank D. Kolodgie, Jan Harnek,et al.Differential Response of Delayed Healing and Persistent Inflammation at Sites of Overlapping SirolimusorPaclitexel-Eluting Stents.Circulation,2005;112:270～278

[7] Michael C John,Rainer Wessely, Adrian Kastrati,et al.Differential Healing Responses in Polymer-and Nonpolymer-Based Sirolimus-Eluting Stents J Am Coll Cardiol Intv, 2008; 1:535～544

智慧广场——重叠问题 篇3

教学目标:

1、经历集合图的产生过程, 能借助直观图, 利用集合的思想方法解决简单的重叠问题, 突出解决问题策略的多样性。

2、经历探究的过程, 在自主探究与合作交流中学习、发展, 体验重叠问题建模的过程, 并初步感知数学的严密逻辑。

3、在积极主动参与数学活动的过程中体验数学的价值, 获得成功的体验, 提高学习数学的兴趣。

教学重点:使学生初步体会集合的有关思想方法, 并能用来解决实际问题。

教学难点:理解有重复时, 应从和中减去重复部分。

教学过程:

一、谈话交流, 明确重叠

师:我们记录了三年级一班同学参加实践活动的情况:

小记者:一共6人 小交警:一共5人

如要求参加社会实践活动的一共有多少人?你会解决吗?

预设:6+5=11 (人)

谈话:实际情况是这样吗?我们仔细观察:

预设:6+5-2=9 (人)

二、深入探究、建立模型

1、组织比赛, 制造矛盾

谈话:老师为每组同桌准备了一个磁力板, 上面有队员名单和各队员的名牌。比赛在同桌两人之间进行。游戏规则是:

(1) 左边同学是小记者队的队长, 右边同学是小交警队的队长。

(2) 每个队长根据队员名单抢各自队员的名牌。

(3) 把抢到的名牌按名单的顺序摆在磁力板上, 抢齐名牌的同学获胜。

读懂规则了吗?开始比赛。

2、分析游戏结果

师:谁抢到了所有的名牌?

你们是怎样赢得比赛的?

有同位比出了胜负, 其他同位呢?

没比出胜负的小组各自抢到了几张名牌?少了谁?为什么会这样呢?

预设:有2个同学既参加了小记者队又参加了小交警队, 而名牌只有一个, 如果让小记者队长抢走, 交警队长这里就少了, 如果让小交警队长先抢走了, 小记者队这边就少了。

师:刚才赢的同学为什么会抢到所有的名牌?

师:有没有办法让两个同学都赢呢?

引导:这2张名牌摆在哪里能让两个人都满意?同桌两人在磁力板上摆摆试试。

3、小组合作, 解决双赢方案

全班交流, 说说你们怎样想的?

预设:摆在中间, 从这小记者这边看, 是小记者队的队员, 从小交警这边看, 是小交警队的队员。

三、拓展应用、形成技能

三年级二班参加艺术节比赛的同学一共有多少人?

谈话:现在的韦恩图里, 连符号都不出现了, 直接出现各部分的数量, 就变得更简单了, 咱们同学能看懂吗?

学生独立解决, 全班交流, 订正。

井有多深?

提问:什么叫接头处吗?

学生独立计算, 全班交流。

3、三年级一班同学一共有45人, 在班级饮食调查中发现, 喜欢吃蔬菜的同学有14人, 喜欢肉食的同学有26人, 既喜欢吃肉食又喜欢吃蔬菜的同学有10人, 两样都不喜欢的有15人。

谈话:我们一起先用画图理解, 红色部分表示什么意思?蓝色部分表示什么意思?黄色部分呢?两样都不喜欢的同学在哪里?你是属于哪部分里的?你想对这些同学说点什么?

四、全课总结、回顾整理

谈话:今天我们一起来研究了重叠问题, 先根据同学们参加社会实践活动的情况, 提出了问题;然后一起玩了抢名牌的游戏, 学习韦恩图;接下来找到了解决重叠问题的规律和方法;最后通过解决生活中的问题, 加深了对重叠问题的理解。