虽然已经说过graph mining不再是我自己最感兴趣的重点，但是处于延续性已经还有若干没有毕业的这个方向的硕士生和博士生，我打算在接下来2年做一些以下方面的工作，供大家参考（部分摘选自基金申请书）。

----

网络信息挖掘是通过已观测到的信息，来挖掘或者说预测未知的信息，包括（1）再现缺失信息，例如链路预测[1,2]和个性化推荐[3,4]；（2）剔除错误信息[5]；（3）挖掘网络结构和功能中的关键节点[6-9]；（4）利用网络观测到的动力学信息去追溯动力学初始发生的状况[10]，或反向推断网络结构的信息[11]；（5）预测网络节点度未来的增长[12]；等等。

（一）通过消相干技术，挖掘网络马尔科夫动力学中的关键节点。网络上的马尔科夫动力学具有两个主要的特征：（1）网络上节点状态变化的动力学是离散时间的；（2）网络上任意节点下一时刻的状态只和本时刻与其相连的节点的状态有关。网络中包含传播、同步、扩散在内的多种动力学过程都是典型的马尔科夫动力学。计算网络中任意给定的一个节点或一组节点的对动力学的影响力的前提是对动力学过程本身有精准的认识，然后传统的解析方法往往只在网络每一个局部都是树状结构，动力学不存在局部性的前提下才足够精确，因为复杂的环路结构会带来很多动力学的相干[13,14]。最近尝试用非回溯矩阵（non-backtracking matrix）来替代邻接矩阵或拉普拉斯矩阵对网络上的传播[15]、渗流[16]和级联动力学[17]进行分析，可以获得更精确的结果，但只是部分消除了名为“回声效应”[18]的一种最简单的动力学相干。因此，依然需要更深入的方法来去掉更高阶的关联。这部分深入的研究可望解决网络动力学中具有基础性和普适性的难题，进而指导精准计算和挖掘网络中的关键节点和节点群。

（二）基于网络信息挖掘的压缩和抽样的理论与方法。随着信息技术的快速发展，目前我们需要处理的网络规模越来越大，例如社交网络节点数动辄数亿甚至超过10亿，物联网络号称短期内会达到百亿节点规模，而WWW早已经超过万亿网页。在网络充分大的情况下，只能通过压缩（去掉一些连边但保持网络节点数不变）或者抽样（网络节点数减少）的方式进行高效的数据存储、传输和分析[19,20]。遗憾的是，目前尚没有广泛认可的评价压缩或抽样效果的标准，没有高效的算法，也没有在给定限制条件下估计压缩比极限的理论方法。我认为比较网络压缩或抽样前后信息挖掘的效果，是一种合理而可行的方法，但是这方面基本上只有一些零星粗糙的研究[21]，且缺乏理论分析。将尝试给出较完整的抽样和压缩理论，包括抽样和压缩的评估标准和高效算法，并在网络中关键节点的识别、个性化推荐等不少于2个关键场景，实现用10%的数据达到90%的算法精确度。

（三）具有重大社会经济价值的应用研究。拟利用网络信息挖掘的理念和算法，尝试解决若干具有重大社会经济价值的现实问题，包括：（1）通过对中国数千万企业之间投资关系网络的分析（最近有银行间金融关系网络的分析，但是网络规模很小[22,23]），发现最容易导致金融经济风险的行业和企业，建立金融经济风险传播的动力学模型，实现风险的提前感知和预警，并为有效的干预手段提供参考；（2）通过对电商网站、维基百科等典型互联网场景海量用户行为数据进行统计分析和建模[24]，应用网络信息挖掘技术，不仅剔除随机噪音数据，还能够进一步甄别因为商业、政治或其他目的，蓄意造假的数据；（3）在给定少量已经别识别为危险节点的前提下，尝试精准识别其余节点中风险最高的节点，该问题尚无系统化的研究，但可以应用于致病基因识别、邪教和暴恐人员识别、传染病早期高危人群识别等重要问题上。

（一）和（三）的（1）（3）我相对更感兴趣一些！！

重要参考文献：

[1] A. Clauset, C. Moore, M. E. J.Newman, Nature 453, 98 (2008).

[2] L. Lu, L. Pan, T. Zhou, Y.-C. Zhang, H. E.Stanley, PNAS 112, 2325 (2015).

[3] T. Zhou, Z. Kuscsik, J.-G. Liu, M. Medo, J. R. Wakeling,Y.-C. Zhang, PNAS 107, 4511 (2010).

[4] L. Lu, M. Medo, C.-H. Yeung,Y.-C. Zhang, Z.-K. Zhang, T. Zhou,Phys. Rep. 519, 1 (2012).

[5] R. Guimera, M. Sales-Pardo,PNAS 106, 22073 (2009).

[6] M. Kitsak, L. K. Gallos, S.Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, H. A. Makse, Nat. Phys. 6, 888(2010).

[7] F. Morone, H. A. Makse, Nature524, 65 (2015).

[8] L. Lu, T. Zhou, Q.-M. Zhang, H. E. Stanley, Nat. Commun. 7, 10168(2016).

[9] L. Lu, D. Chen, X.-L. Ren,Q.-M. Zhang, Y.-C. Zhang, T. Zhou,Phys. Rep. 650, 1 (2016).

[10] P. C. Pinto, P. Thiran, M.Vetterli, Phys. Rev. Lett. 109, 068702 (2012).

[11] X. Han, Z. Shen, W.-X. Wang,Z. Di, Phys. Rev. Lett. 114, 028701 (2015).

[12] D. Wang, C. Song, A.-L.Barabasi, Science 342, 127 (2013).

[13] R. Pastor-Satorras, C.Castellano, P. Van Mieghem, A. Vespignani, Rev. Mod. Phys. 87, 925 (2015).

[14] W. Wang, M. Tang, H. E.Stanley, L. A. Braunstein, Rep. Prog. Phys. 80, 036603 (2017).

[15] B. Karrer, M. E. J. Newman,Phys. Rev. E 82, 016101 (2010).

[16] B. Karrer, M. E. J. Newman,L. zdeborova, Phys. Rev. Lett. 113, 208701 (2014).

[17] F. Radicchi, Nat. Phys. 11,597 (2015).

[18] F. Radicchi, C. Castellano,Phys. Rev. E 93, 030302 (2016).

[19] M. P. Stumpf, C. Wiuf, R. M.May, PNAS 102, 4221 (2005).

[20] D. D. Heckathorn, C. J.Cameron, Annual Rev. Sociology (in press, 2017).

[21] J.-D. J. Han, D. Dupuy, N.Bertin, M. E. Cusick, M. Vidal, Nat. Biotech. 23, 839 (2005).

[22] A. G. Haldane, R. M. May,Nature 469, 351 (2011).

[23] M. Bardoscia, S. Battiston,F. Caccioli, G. Caldarelli, Nat. Commun. 8, 14416 (2017).

[24] Y. Zha, T. Zhou, C. Zhou, PNAS 113, 14627 (2016).