网络聚类算法及其生物信息学应用

介绍一些网络聚类算法及其基本原理,简述了其在生物信息学的应用。本文不是一个网络聚类算法的全面综述,只介绍这些网络聚类算法的基本思路,体会其数学建模的基本思想。     

开源设计网络社区的用户聚类研究

为了对开源设计网络社区中的用户进行细分研究,首先采用复杂社会网络技术建立了社区组织的复杂网络模型.其次,根据用户在社区中的三种行为设立了备选指标,并通过指标聚类的方法对指标进行筛选,保证了聚类指标的全面性和代表性.在此基础上,以OpenIDEO为研究案例,采用K-Means算法对该社区中的用户进行了聚类,根据聚类结果将用户分为了创新型用户、传播型用户和普通用户,并进一步分析了各类用户的特点及参与动机.聚类结果表明,所提出的聚类指标及算法可以清晰地识别出开源社区的用户类型及占比,为开源设计社区管理机制和激励措施的优化提供了准确的依据.     

基于企业网络舆情的客户满意度分析及管理方法

社交网络平台的迅速发展,促使网络舆情成为企业获取商业情报、扩大竞争优势的重要信息来源。本文针对网络舆情环境下的企业客户关系管理问题展开研究。通过构建企业客户推动式信息反馈模型,描述了企业客户、网络用户与企业网络舆情间的联系,并依据信息反馈模型,提出变尺度聚类算法。该算法将传统聚类方法的求解过程由单一尺度分析扩展到多尺度分析,克服了实际数据聚类应用过程中的聚类结果特征不显著问题。本文选取新浪微博作为数据源,利用企业网络舆情数据集和企业客户数据集进行数据分析实验。实验结果表明,企业可以通过获取与其主营业务相关的网络舆情信息,实现客户满意度预测;同时,变尺度聚类算法结果能够为企业进一步制定销售战略和销售战术提供决策支持。     

组织特异性蛋白质复合体的识别

本文研究了组织特异性蛋白质复合体的识别问题.利用蛋白质相互作用网络数据以及组织特异性基因表达数据构建组织特异性蛋白网络,利用多种代表性聚类算法对该网络进行聚类,并利用非负矩阵分解对聚类结果进行合并聚类,得到了组织特异性蛋白质复合体.结果表明,聚类效果得到明显提升,并且能识别出组织特异性蛋白质复合体.     

基于中心平面的聚类模型及在电商中的应用

因为k-平面聚类算法(kPC)和k-中心平面聚类算法(kPPC)构建的聚类中心平面是无限延伸的,这会影响聚类的性能,所以提出了局部的k-中心平面聚类(L-kPPC)算法.此算法在kPPC中引入了k-均值聚类算法(k-mean),这样使得样本点都聚集在类中心周围.L-kPPC利用了各聚类中心平面的局部特征构建类中心平面,使同一类的数据点到此类的聚类中心或平面尽可能的近,离其他类中心或平面尽量远,这导致求解特征值问题.在此,利用拉普拉斯图建立初始化的数据点,而不是随机选择的初始数据点.最后从电商平台ebay提供的Web Service接口提得数据进行实验,实验结果分析表明,L-KPPC算法有较好的表现.     

函数型聚类分析:基于距离的一步法框架

基于距离的函数型聚类分析包含曲线拟合和聚类两个独立步骤,最优曲线拟合未必有利于类别信息的提取和保留。根据曲线拟合与聚类分析的计算过程,重新梳理了函数型聚类算法;基于距离度量,提出了同时考虑拟合和聚类效果的函数型聚类一步法;在交替方向乘子法(ADMM)框架下推导并给出了迭代求解算法。模拟试验结果显示,该函数型聚类算法有助于提高聚类精度;针对北京市空气质量监测站点二氧化氮(NO_2)污染物小时浓度数据的实例验证分析表明,该函数型聚类算法对不同类别空气质量监测点具有更好的区分度。     

一个新的模糊聚类有效性指标

提出了一个判别模糊聚类中聚类数有效性的新指标.首先利用FCM算法对数据集进行模糊聚类,通过隶属度矩阵和聚类中心构建加权二分网络.然后通过改进加权二分网络的模函数,定义一个新的聚类有效性指标.为了检验该有效性指标的性能,选取了三个常见的有效性指标在十五个数据集上进行了对比.实验结果表明,该有效性指标具有较好的性能.     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

一种改进差分进化的自动聚类算法研究

K-means算法需要提前确定聚类数量和初始聚类中心.为了解决这个问题,提出了一种基于改进的差分进化算法DVDE的自动聚类算法(AC-DVDE).使用双交叉策略来添加基于个体间聚类的随机交叉策略,用于在传统的两点交叉操作之后的自动聚类中使用的特定编码方法;提出了用于聚类中心选择的随机交叉策略,聚类中心很可能偏离数据集或聚类中心太过集中的问题,通过改进,有效地避免算法本身随机性的错误聚类划分,首先筛选聚类中心,再进行聚类.通过比较UCI的四个数据集的仿真结果,提高了算法的聚类精度和稳定性,具有一定的价值.     

一种新的概率神经网络有监督学习算法

提出一种新的PNN有监督学习算法:用学习矢量量化对各类训练样本进行聚类,对平滑参数σ和距离各类模式中心最近的聚类点构造区域,并采用遗传算法在构造的区域内训练网络,实验表明:该算法在分类效果上优于其它PNN学习算法。     

A matrix modular neural network based on task decomposition with subspace division by adaptive affinity propagation clustering

In this paper, a matrix modular neural network (MMNN) based on task decomposition with subspace division by adaptive affinity propagation clustering is developed to solve classification tasks. First, we propose an adaptive version to affinity propagation clustering, which is adopted to divide each class subspace into several clusters. By these divisions of class spaces, a classification problem can be decomposed into many binary classification subtasks between cluster pairs, which are much easier than the classification task in the original multi-class space. Each of these binary classification subtasks is solved by a neural network designed by a dynamic process. Then all designed network modules form a network matrix structure, which produces a matrix of outputs that will be fed to an integration machine so that a classification decision can be made. Finally, the experimental results show that our proposed MMNN system has more powerful generalization capability than the classifiers of single 3-layered perceptron and modular neural networks adopting other task decomposition techniques, and has a less training time consumption.     

基于网络等级特征与VMS的交叉巢式Logit模型

基于等级特征与可变信息板(VMS)研究了交叉巢式Logit(CNL)模型及网络交通流分配。综合幂函数与指数函数表示方法给出新的信息效用衰减因子,结合道路等级特征表示VMS对车流的影响系数及CNL模型的分配系数;给出等级结构道路网络的随机用户均衡条件下的交叉巢式Logit路径选择模型及其等价数学规划,并设计网络流分配算法。通过实例网络的计算与分析,得到一些有意义的结论:等级结构越显著的路网总出行时间费用越低且其分散参数(θ)弹性绝对值越大;对具有较强随机性的实际路网,若增加一定的确定性则节省更多网络总出行时间;道路网络中设置了VMS时总出行时间受分散参数的影响更小。     

Optimal hierarchical system of a grid road network

This paper develops a simple analytical model for determining the hierarchical system of road networks. The model is based on a grid road network where roads are classified into three types according to road widths and travel speeds. We derive the optimal ratios of road areas that minimize the average and maximum travel time. Minimizing the average travel time provides an efficient solution, whereas minimizing the maximum travel time provides an equitable solution. Both of the solutions are expressed in terms of road widths and travel speeds. As an application of the grid network model, we evaluate the hierarchical system of the road network of Tokyo.     

A network traffic flow model for motorway and urban highways

The research reported in this paper develops a network-level traffic flow model (NTFM) that is applicable for both motorways and urban roads. It forecasts the traffic flow rates, queue propagation at the junctions and travel delays through the network. NTFM uses sub-models associated with all road and junction types that comprise the highway. The flow at any one part of the network is obviously very dependent on the flows at all other parts of the network. To predict the two-way traffic flow in NTFM, an iterative simulation method is executed to generate the evolution of dependent traffic flows and queues. To demonstrate the capability of the model, it is applied to a small case study network and a local Loughborough–Nottingham highway network. The results indicate that NTFM is capable of identifying the relationship between traffic flows and capturing traffic phenomena such as queue dynamics. By introducing a reduced flow rate on links of the network, the effects of strategies used to carry out roadworks can be mimicked.     

Agent-based modelling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies

This study investigates the effectiveness of simultaneous and staged evacuation strategies using agent-based simulation. In the simultaneous strategy, all residents are informed to evacuate simultaneously, whereas in the staged evacuation strategy, residents in different zones are organized to evacuate in an order based on different sequences of the zones within the affected area. This study uses an agent-based technique to model traffic flows at the level of individual vehicles and investigates the collective behaviours of evacuating vehicles. We conducted simulations using a microscopic simulation system called Paramics on three types of road network structures under different population densities. The three types of road network structures include a grid road structure, a ring road structure, and a real road structure from the City of San Marcos, Texas. Default rules in Paramics were used for trip generation, destination choice, and route choice. Simulation results indicate that (1) there is no evacuation strategy that can be considered as the best strategy across different road network structures, and the performance of the strategies depends on both road network structure and population density; (2) if the population density in the affected area is high and the underlying road network structure is a grid structure, then a staged evacuation strategy that alternates non-adjacent zones in the affected area is effective in reducing the overall evacuation time.     

随机交通网络渐近连通可靠性分析

应用原有拓扑法获得城市交通网络的拓扑结构图,利用对偶拓扑法得到交通网络的对偶图,建立交通网络的随机网络模型。定义交通网络的渐近连通可靠性,得到路段连通可靠性、路网规模及整个路网连通可靠性之间的定量关系,结合随机图论、大数定律、渐近方法等证明所得结论;通过实例说明结论的应用价值。     

Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge

The minimum cost path problem in a time-varying road network is a complicated problem. The paper proposes two heuristic methods to solve the minimum cost path problem between a pair of nodes with a time-varying road network and a congestion charge. The heuristic methods are compared with an alternative exact method using real traffic information. Also, the heuristic methods are tested in a benchmark dataset and a London road network dataset. The heuristic methods can achieve good solutions in a reasonable running time.     

A non-smooth model for signalized road network design problems

A signalized road network is considered where the set of link capacity expansions and signal setting variables are simultaneously determined. This paper addresses a new optimization scheme for a signalized road network design problem (SRNDP). A SRNDP can be formulated as a mathematical program with equilibrium constraints (MPEC) where user equilibrium is expressed as a variational inequality problem. Due to non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth model is established. A bundle subgradient projection (BSP) method is presented with global convergence. Numerical calculations are conducted on a real data city road network and large-scale grid networks where promising results are obtained.     

Optimization Models for Forest Road Upgrade Planning

Road blocking due to thawing or heavy rains annually contribute to a considerable loss in Swedish forestry. Companies are forced to build up large stocks of raw material (saw and pulp logs) in order to secure a continuous supply when access to the road network is uncertain. Storage outdoors leads to quality deterioration and monetary losses. Other related costs due to road blocking are road damage and longer haulage distances. One approach to reduce the losses due to road blocks is to upgrade the road network to a standard that guarantees accessibility. We consider the road upgrade problem from the perspective of Swedish forest companies with a planning horizon of about one decade. The objective is to minimize the combined upgrade and transportation costs. We present two mixed integer programming models, which are uncapacitated fixed charge network flow problems including multiple assortments, several time periods and a set of road classes. One model is based on arc flows and one on route flows. For a typical planning instance, the models become large and we propose how to improve solution performance through model strengthening. The models are tested in a case study for a major Swedish forest company.      

City expansion model based on population diffusion and road growth

In this paper, a city expansion model is proposed to capture the coevolution relationship between population diffusion and road growth. In the model, we adopt the physical diffusion process, which considers the influence of the road network topology and random exploration factor, to analyse the population diffusion based on the cellular automata (CA) model. In addition, the growth mechanism of the road network is developed to minimize the construction cost related to the population density and the Euclidean distance. The distribution complexities of the population density and the road network topology in the evolution process are then analysed. Compared with the real Beijing city in 2012, the suggested model can be used to describe the city evolution process.