现在很多复杂网络都是高度异质的，网络中的节点和链路扮演着很不一样的角色，因此识别网络中的关键节点非常重要。特别地，我们需要识别在不同的动力学下（例如SIR，SIS，Percolation，Routing，Game等等），网络节点的重要性。这些动力学我们暂且叫他们目标动力学（target dynamics）。    

   这方面的研究中，99%的指标都是结构性指标（structural），例如节点度和各种各样的中心性指标（centralities，推荐大家看两篇很好的论文[1-2]），还有最近提出的一些指标，例如k-shell index[3]和H指数[4]。这些指标之所以被叫做结构性指标，是因为它们反映的是网络结构上的重要性，而计算它们也只需要结构信息。

   还有一类指标看起来似乎用到了动力学，例如PageRank和它的若干变种（又推荐大家看两篇很牛逼的综述论文[5-6]），但是实际上没有考虑到真正在网络中进行的动力学，因为跑在网络上的动力学（例如带随机重启的随机游走是PageRank的动力学），是用来量化网络节点的重要性的一种手段或工具，而不是这些节点真正要面对的目标动力学。

   我这里想给大家介绍的，是考虑了目标动力学的性质或者参数的一些挖掘关键节点（本质上就是衡量节点重要性）的方法。这些指标往往表现地比结构性指标要好，但是这并不意外，因为它们考虑了目标动力学，所以这种对比实际上是不公平的。那为什么要研究和设计这类指标呢？是因为有一些动力学特别重要（例如传播动力学[7]），而悲惨的是，在不同的动力学参数条件下，网络中节点重要性的排序变化非常大[8]，这就使得如果不考虑动力学的性质和参数，实际上没有办法得到任何有效排序。

   为了方便大家，我把这些指标分成3个大类。下面简单就每一类的代表性工作进行介绍，具体的细节，大家要看参考文献。

   （1）路径计数（Path Counting）。路径计数是最常见的一种办法，实际上，很多结构性指标也采用类似的思路。最具代表性的一个指数是“动力学影响力”（dynamical influence）[9]。用向量x表示节点的状态，节点的动力学如果是一个Markov动力学，可以写成x(t+1)=Mx(t)，那么可以证明节点i（以收敛状态为考量）的影响力DI(i)是对应于M的最大特征值的左特征向量在i节点上的分量。有些学者觉得这应该分类为Laplacian-basedcentrality，我不太赞同，因为很多结构性指标也是Laplacian-based centralities，而且这样说几乎所有的Markov动力学的影响力指标都可以归为Laplacian-based。之所以我认为这是一种路径计数，是因为如果把M看成邻接矩阵（虽然它不是），计算对应于M的最大特征值的左特征向量的幂迭代（power iteration）办法实际上是数从每个节点出发的长度为L的不同路径数目，然后求L为无穷时候的极限。实际上，Pei和Makse的综述中也把Klemm等人的工作归入到path counting中[10]。Klemm等人注意到针对SIR模型，如果传染率正好在临界值，那么DI会退化到结构性指标中的特征向量中心性。类似地结果对于SIS模型也是适用的[11]。利用Path counting的思路，Ide等人[12]给出了对于著名的AlphaCentrality[13]的一种新理解：Alpha centrality可以直接用来刻画SIR模型节点的影响力，其中在Alpha centrality中的参数alpha=beta/delta，其中beta是传染率，delta是恢复率。这个工作虽然没有给出任何“新的指标”，但我特别喜欢，因为一下子给了我新的深刻洞见。最勇敢无畏的办法要算Bauer和Lizier[14]，这哥儿俩真的要把所有的路径数目数出来，其中计算路径的时候，他们有一种“有效路径”的变换，把动力学参数考虑进去了。不管怎么样，这个方法的复杂性让人恐怖（可以独立性的假设实际上也不成立）——作者自己也意识到了这点，因为在一个芝麻大的网络上做试验（路径长度还做了截断），要用2000小时。但是我非常建议读者看看这个方法，因为它最最明确地表达了pathcounting的精髓，而如果以后这方面的近似做得更好了，Bauer和Lizier的思路应该会很有效。如果要勉强一点，路由的中心性也可以算作pathcounting，当然，前提是路由表已经固定下来了[15]。

   （2）含时方法（Time-Aware Methods）。这方面的研究不多，有代表性的工作我只注意到两个。一个是Ghanbarnejad和Klemm对于布尔动力学的分析[16]。针对一个一般性的布尔动力学，他们抽象出了一个激活矩阵A(activitymatrix)，其中矩阵元A(i,j)表示节点i的状态如果发生变化，会有多大概率引起j的状态变化。这里面假设网络节点2^N个状态向量出现的概率是一样的，而这显然是一个不正确的假设。不管怎么样，有了A，就可以有A^2，A^3等等，从而得到节点i上的状态微扰对于t时步之后整个系统状态的改变总量，并用其来度量i的影响力。遗憾的是，作者一直没有说清楚如果i在t个时步里面把j变了两次，到底算2还是算0，因为j的状态看起来是没有变化的。这个文章漏洞很多，后面还有更不可思议的有向树假设（大家自己看），但是分析布尔动力学节点影响力的思路或许有可以借鉴的地方。我们最近做了一个工作[17]，我觉得非常干净漂亮得到了离散情况下考虑t时步后SIR动力学传染状态的节点影响力指标（具体大家看论文）。让人郁闷的是，文章发表后我才注意到这个指标实际上是Alpha centrality的一个有限时间截断。尽管Alpha centrality完全没有讨论SIR有限时间步的问题，但是这还是让我对Alpha centrality更加尊重——就象看了前三盘棋之后柯洁对AlphaGo的态度。

   （3）其他妖法（Others）。这部分就不多介绍了，反正千奇百怪的方法都有，主要是在什么叫“节点重要性”方面给出了很多稀奇古怪的定义，很有趣（实际上文献[11]也有一些创新性的定义，尽管靠谱程度还要打个问号）。比如说怎么定义一个节点对于演化博弈的影响力[18]，对于渗流的影响力[19]，等等。特别说一个段子，Sikic有一种方法是把节点simulation出来的重要性在整个SIR动力学参数空间中求平均值，然后和k-shell等指数比较。等于是已经知道了所有的答案，然后假装不知道，故意求个平均，然后选几个特殊的点和结构性指标比[8]。我也是无语了！但是还是很佩服Sikic，至少他们给出了翔实的模拟结果，说明动力学指标的重要性。

参考文献：

[1]Borgatti, S. P. (2005). Centrality and network flow. Social networks, 27(1),55-71.

[2]Borgatti, S. P., & Everett, M. G. (2006). A graph-theoretic perspective oncentrality. Social networks, 28(4), 466-484.

[3]Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., & Makse, H. A. (2010). Identification of influential spreaders incomplex networks. Nature physics, 6(11), 888-893.

[4]Lü, L., Zhou, T., Zhang, Q. M., & Stanley, H. E. (2016). The H-index of anetwork node and its relation to degree and coreness. Nature communications, 7,10168.

[5]Gleich, D. F. (2015). PageRank beyond the Web. SIAM Review, 57(3),321-363.

[6]Ermann, L., Frahm, K. M., & Shepelyansky, D. L. (2015). Google matrixanalysis of directed networks. Reviews of Modern Physics, 87(4),1261.

[7]Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A.(2015). Epidemic processes in complex networks. Reviews of modern physics, 87(3),925.

[8]Šikić, M., Lančić, A., Antulov-Fantulin, N., & Štefančić, H. (2013).Epidemic centrality—is there an underestimated epidemic impact of networkperipheral nodes?. The European Physical Journal B, 86(10),1-13.

[9]Klemm, K., Serrano, M. Á., Eguíluz, V. M., & San Miguel, M. (2012). Ameasure of individual role in collective dynamics. Scientific reports, 2,292.

[10]Pei, S., & Makse, H. A. (2013). Spreading dynamics in complex networks.Journalof Statistical Mechanics: Theory and Experiment, 2013(12),P12002.

[11]Li, P., Zhang, J., Xu, X.-K., & Small, M. (2012). Dynamical influence ofnodes revisited: A Markov chain analysis of epidemic process on networks.Chinese Physics Letters, 29(4), 048903.

[12]Ide, K., Zamami, R., & Namatame, A. (2013). Diffusion Centrality inInterconnected Networks. Procedia Computer Science, 24, 227-238.

[13]Bonacich, P., & Lloyd, P. (2001). Eigenvector-like measures of centralityfor asymmetric relations. Social networks, 23(3),191-201.

[14]Bauer, F., & Lizier, J. T. (2012). Identifying influential spreaders andefficiently estimating infection numbers in epidemic models: A walk countingapproach. EPL (Europhysics Letters), 99(6), 68007.

[15]Dolev, S., Elovici, Y., & Puzis, R. (2010). Routing betweenness centrality.Journalof the ACM (JACM), 57(4), 25.

[16]Ghanbarnejad, F., & Klemm, K. (2012). Impact of individual nodes in Booleannetwork dynamics. EPL (Europhysics Letters), 99(5),58006.

[17]Liu, J. G., Lin, J. H., Guo, Q., & Zhou, T. (2016). Locating influentialnodes via dynamics-sensitive centrality. Scientific Reports, 6, 21380.

[18]Simko, G. I., & Csermely, P. (2013). Nodes having a major influence tobreak cooperation define a novel centrality measure: game centrality. PloSone, 8(6),e67159.

[19]Piraveenan, M., Prokopenko, M., & Hossain, L. (2013). Percolationcentrality: Quantifying graph-theoretic impact of nodes during percolation innetworks. PloS one, 8(1), e53095.