模块度

模块度（Modularity）的概念。以无向网络为例，假设L为网络中所有边的个数。当我们把此网络划分为Nm个模块时，若s 为其中一子模块，而 ls为子模块中边数之和，ds为子模块中点的数之和，则模块度可表示为：sigma(1->Nm)(ls/L)-(ds/2*L)^2(见纸质版)。在确定了模块度的定义后，则鉴定基因模块的算法就是去如何优化模块度的最大值。在针对如何优化模块度的问题时，现有的算法大致采取两种策略：（1）随机算法（这里暂定为模拟退火法）(6，7)；(2)贪心法（greedy）（7）。模拟退火法为随机算法的一种，它以物理中的固体退火为原理进行实现。因为算法能够以Metropolis准则接受次优解，所以从根本上避免了走入局部最优解的陷阱（尽管当温度趋于0的时候算法类似局部搜索法）。在此方法中，新解得产生过程为:随机合并两个子模块或者随机分开一个子模块以及随机交换两个不同子模块之中的任意两个点，其中每次降温过程共进行点交换 次，子模块运算次，降温次数视降温系数，初始温度，最优解重复次数而定（一般需要降温几千次）。算法特点为以较小的代价获得较优的解。尽管模拟退火法的结果较为准确，但其非常费时，只能适用于小规模的生物网络。而贪心算法尽管可以在较短时间对大规模生物网络进行分析，但其得到的模块有精确度较低的缺点。