一种新的拓扑参数及其蛋白质网络 关键节点识别 *

针对已有拓扑参数对关键蛋白识别度不高的现状，根据蛋白质网络的特点，结合参数计算方法，提出一 个新的用来描述节点重要性的拓扑参数—— —点覆盖参数。为了避开该参数精确求解方法中可能出现的NP- 难 问题，从稀疏网络出发，在研究低度点核化技术的基础上，将确定算法与非确定算法相结合，提出基于随机核化 的快速算法（A_R_K算法）。实验结果显示，所获得的点覆盖参数不仅可以有效地描述网络节点的拓扑重要性， 而且其关键蛋白识别度也明显高于其他参数。

New topological parameter for recognition of essential node in protein networks

For the low recognition degree in the identification of essential protein based on topological parameter,this paper proposed a new parameter-vertex cover parameter(VP) to describe the importance of a node in a network in virtue of parameterized computation.To avoid the NP-hard which probable met in the process of getting the parameter with exact methods,studied the kernelization by low degree nodes and the combination of exact and no-exact algorithms according to the sparseness of protein networks,and put f...