基于边状态枚举计算多状态网络可靠度动态界

为降低计算多状态网络可靠度的复杂性,综合考虑网络中具有多态性的边处于各中间状态的概率及从某中间状态转换到相邻状态对网络性能的影响,提出了一种基于边状态枚举计算多状态网络可靠度上下界的算法.该算法首先令网络中各边仅取完全工作和完全失效两种状态,将处于中间状态的概率分别叠加到完全工作和完全失效状态的概率上,得到可靠度上下界的初始值;而后按照对可靠度影响递减的顺序迭代枚举边的中间状态,通过集合间的比较,计算可靠度上下界的改变值,同时获得不断减小的可靠度上界和不断增加的可靠度下界,使其最终收敛于可靠度精确值.该算法不需提前求取网络d-最小割(路)集,且枚举较少的网络状态即可得到紧凑的可靠度上下界.相关引理的证明及算例分析验证了该算法的正确性和有效性.     

双网络中影响力凝聚子图发现算法

双网络由物理图和概念图构成，其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系；概念图中边表示结点间的相似程度，通常由计算得出.最近，从双网络中发现凝聚子图，即物理图中连通且概念图中稠密的子图受到研究者的广泛关注，在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此：1）提出一种基于最小边权重定义的影响力凝聚子图，即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒. 2）由证明可知，发现影响力最大的k-ICT子图是NP-难的，因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图，能够根据不同的k值，快速发现包含所有k-ICT子图的候选子图. 3）提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT，用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验，验证算法的高效性和有效性.     

基于边分割的社交网络敏感边保护技术

用户间的敏感关系是社交网络中用户的重要隐私信息。为了解决社交网络中用户间敏感关系泄露问题,提出一种边分割算法。首先,将已删除敏感边的简单匿名社交网络的非敏感边分割成多条子边;然后,将原非敏感边携带的信息分配到子边上,使得每条子边只携带原非敏感边的部分信息,从而生成具有隐私能力的匿名社交网络。理论分析和仿真实验结果表明,相比cluster-edge和cluster-based with constraints算法,边分割算法在保证数据具有较高可用性的情况下能更大限度降低敏感关系泄露的概率,泄露概率分别降低了约30%和20%,因此所提算法能够有效解决社交网络中敏感关系泄露问题。     

一种基于极大连通子图的电信社群网分割算法

随着电信事业的发展,电信社群网的分析逐渐兴起。根据电信数据的特点,以关系数据库为基础,实现了一个极大连通子图求解算法（MCSG）。该算法利用等价类的概念实现了图数据分层处理,利用边标识法表示极大连通子图,确保了结果中顶点和边信息的完整性。实验表明,MCSG算法有效实现了对电信社群网的分割。     

模拟电路网络撕裂法的子网络划分方案优选

针对模拟电路网络撕裂方法,研究子网络划分问题,总结了子网络划分时应遵循的基本原则,在此基础上提出了“最大化诊断效率,最小化测试消耗”的子网络划分思想,并从置换激励源,元件、测试点、故障特征灵敏度四方面对子网络划分方案的选择做进一步量化分析,提出了优选标准和具体实施步骤,通过仿真实验,验证了方法的可行性和有效性。     

基于可视色差与区域生长的彩色图像分割

提出了一种基于可视色差和分块区域生长的彩色图像分割算法,首先将待处理图像划分成若干大小相同的子块,在CIEL*a*b*颜色空间中计算每个子块的色彩均值和方差值,根据方差值对子块分类,利用可视色差对颜色均匀子块分类、合并,获得初始分割区域,利用四叉树算法对纹理子块分裂合并,然后从初始分割区域开始生长、合并,并删除小颜色块。实验结果证明了算法的有效性,分割结果符合人的主观感知。     

基于加权网络和局部适应度的蛋白质复合物识别算法

蛋白质复合物识别对分析蛋白质网络的结构特征和模块功能具有重要意义。通常在蛋白质网络中挖掘稠密子图或模块来识别其中的蛋白质复合物,限制了其应用范围和识别的准确性。针对该问题,提出了一种基于加权网络和局部适应度的蛋白质复合物识别算法,该算法综合稠密子图的密度指标和模块性定义了新的局部适应度函数,并基于边聚集系数构建加权的蛋白质网络,根据权值选择边,在加权蛋白质网络中将种子边不断聚类扩展,从而获取具有最大综合适应度的子图作为蛋白质复合物。在酵母蛋白质等多个实际网络中试验表明,该算法能够有效提升蛋白质复合物识别的准确性。     

一种基于聚集系数的复杂网络社团划分算法

;社团划分算法是复杂网络研究中的一个热点问题,为发现复杂网络中的社团结构,更好的研究复杂网络的社团性质,本文利用网络中聚集系数提出了一种新的社团划分的算法,该算法综合运用复杂网络中点和边的信息,根据节点和边的聚集系数,计算出节点问的连接紧密程度,由局部到整体来划分出所有的社团结构。传统的复杂网络社团划分算法通过获得全局网络的信息,但随着网络规模的增加,获得全局网络的信息的难度也随之增加,本文提出的新算法避免这一难度所带来的问题。将该算法应用到Zachary空手道俱乐部网络和海豚社会网络,测试结果证明了该算法的可行性。     

基于子块的区域生长的彩色图像分割算法

提出了一种基于图像子块的区域生长算法,应用于彩色图像分割。首先将图像划分成多个不重叠子块,然后利用从CIE L*a*b*颜色空间中提取出的每个子块的颜色和纹理特征,先进行子块内颜色聚类,达到子块分类的目的,再根据生长准则进行基于分类子块的区域生长,实现对自然彩色图像的分割。实验结果证明了算法的有效性,分割结果符合人的主观感知。     

移动异构传感器网络分布式部署算法

针对移动异构传感器网络中的最大覆盖问题,论文提出了一种分布式部署算法.该算法依据节点坐标及其感知范围而更新目标划分子区间,使子区间内的各个节点能结合自身及其delaunay邻居节点当前的几何位置和剩余能量值确定速度向量,同时利用节点的移动特性,使调整后的网络最大化覆盖目标区域.仿真结果表明,该算法在提高网络覆盖率和协调速度的同时,能兼顾网络节点剩余能量的均衡.     

可多边并行移出的社团发现方法

针对GN算法计算效率低下的缺陷,提出一个基于边的中介值测度的发现网络潜在社团结构的新算法。该算法在完成所有边的中介值计算后,利用成分的独立性,采用并行移出各个成分中具有最大中介值的边的方法。通过理论分析,在作为实验测试平台的实际的数据集上进行实验验证,结果表明该算法是快速、有效的。     

基于边聚集系数的社区结构发现算法*

将超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现,引入边聚集系数的概念,提出了基于边聚集系数的社区发现算法。将安然邮件数据集作为测试数据集,通过算法对比分析,证明该算法在时间复杂度上可以提高一个数量级。     

一种有效的社会网络社区发现模型和算法

社会网络的社区发现存在划分效果较好的算法时间复杂度过高、现有快速划分算法划分质量不佳、缺乏表达和充分利用个体和链接属性信息的模型和机制等问题.针对这些问题,提出了一种边稳定系数模型和一种能表达个体间关系紧密度的完全信息图模型,在此基础上设计和实现了一种有效的社区发现算法.提出的完全信息图模型具有较高通用性,适用于需要融合个体和链接属性的社区发现算法.通过系列实验表明,所提出的以边稳定系数模型和完全信息图为基础的算法,对社会网络中的社区发现问题是有效的.算法不仅具有较快的速度,也能适用于带权与不带权的网络,得到的社区划分结果也具有较高的划分质量.     

基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

LPX: Overlapping community detection based on X‐means and label propagation algorithm in attributed networks

Traditional community detection methods in attributed networks (eg, social network) usually disregard abundant node attribute information and only focus on structural information of a graph. Existing community detection methods in attributed networks are mostly applied in the detection of nonoverlapping communities and cannot be directly used to detect the overlapping structures. This article proposes an overlapping community detection algorithm in attributed networks. First, we employ the modified X‐means algorithm to cluster attributes to form different themes. Second, we employ the label propagation algorithm (LPA), which is based on neighborhood network conductance for priority and the rule of theme weight, to detect communities in each theme. Finally, we perform redundant processing to form the final community division. The proposed algorithm improves the X‐means algorithm to avoid the effects of outliers. Problems of LPA such as instability of division and adjacent communities being easily merged can be corrected by prioritizing the node neighborhood network conductance. As the community is detected in the attribute subspace, the algorithm can find overlapping communities. Experimental results on real‐attributed and synthetic‐attributed networks show that the performance of the proposed algorithm is excellent with multiple evaluation metrics.     

Sewage flow optimization algorithm for large-scale urban sewer networks based on network community division

By considering the flow control of urban sewer networks to minimize the electricity consumption of pumping stations, a decomposition-coordination strategy for energy savings based on network community division is developed in this paper. A mathematical model characterizing the steady-state flow of urban sewer networks is first constructed, consisting of a set of algebraic equations with the structure transportation capacities captured as constraints. Since the sewer networks have no apparent natural hierarchical structure in general, it is very difficult to identify the clustered groups. A fast network division approach through calculating the betweenness of each edge is successfully applied to identify the groups and a sewer network with arbitrary configuration could be then decomposed into subnetworks. By integrating the coupling constraints of the subnetworks, the original problem is separated into N optimization subproblems in accordance with the network decomposition. Each subproblem is solved locally and the solutions to the subproblems are coordinated to form an appropriate global solution. Finally, an application to a specified large-scale sewer network is also investigated to demonstrate the validity of the proposed algorithm.     

基于回溯机制的互联网AS拓扑的Betweenness算法

Betweenness能够刻画节点或边在网络中的重要程度．在Internet中，Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量，能够对网络的动态行为进行预测．但传统的Betweenness计算复杂度较高，为O（n^3），但这些算法是为加权网络设计的，而很多实际的网络模型并没有考虑权重．另一方面，目前的算法都没有考虑边的语义，而互联网AS（autonomous system）拓扑中的边具有语义．针对简单无权网络提出一种基于回溯的时间复杂度为O（nm）的Betweenness计算方法．在进一步考虑Internet AS拓扑的特殊性，即任意两个相连的AS都具有某种商业关系的基础上提出了互联网AS层拓扑的Betweenness计算方法．     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

图重构下大规模网络的社团检测算法

对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的链接,这些链接可能会导致模型将来自不同集群的节点划分在一起。为此,提出了基于图重构的社团检测算法（graph reconstruction based community detection,GRCD）,该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构;然后,将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略,即基于话语权的社团组织生成策略;最后,在不同规模数据集上进行实验。实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。     

关系数据库中社区发现方法研究

文中在研究了现有社区发现算法的基础上,提出了一种简单的加权网络中社区发现方法。文中基于社区结构最为普遍的性质,受社会网络中真实社区结构和并行计算的任务划分规则的启发,提出了基于核心边的加权网络中社区发现方法。该方法首先依据网络中边的权值寻找核心边;然后依据相似性度量,发现网络中的一个初始社区;最后通过隶属度度量,将发现的初始社区逐步扩展成网络中的社区结构。该方法在进行社区结构发现的过程中,仅仅依赖节点所处位置的局部信息,可以在对网络进行广度优先遍历的过程中完成社区发现工作。因此该方法具有较低的计算复杂度,可以适用于大规模网络中的社区发现。通过有效性实验和效率实验,表明该方法可以有效发现大规模网络中的社区结构。