·228 智能系统学报 第12卷 Lu Linyuan.Link prediction on complex networks[.Jour- [20]HANLEY J A,MCNEIL B J.The meaning and use of the nal of university of electronic science and technology of Chi- area under a receiver operating characteristic (ROC)curve na,2010,39(5):651-661. [J].Radiology,1982,143(1):29-36. [9]Lu Linyuan,ZHOU Tao.Link prediction in complex net- [21]HERLOCKER J L,KONSTAN J A,TERVEEN L G,et works:a survey[J].Physica A:statistical mechanics and al.Evaluating collaborative filtering recommender systems its applications,2011,390(6):1150-1170. [J].ACM transactions on information systems,2004,22 [10]GETOOR L,DIEHL C P.Link mining:a survey [J]. (1):5-53. ACM SIGKDD explorations newsletter,2005,7(2):3- [22]ZHOU Tao,REN Jie,MEDO M,et al.Bipartite network 12. projection and personal recommendation[J].Physical re- [11]LIBEN-NOWELL D,KLEINBERG J.The link prediction view E,2007,76(4):046115. problem for social networks[J].Journal of the American [23]FAWCETT T.An introduction to ROC analysis[J].Pattern society for information science and technology,2007,58 recognition letters,2006,27(8):861-874. (7):1019-1031. [24]LORRAIN F,WHITE H C.Structural equivalence of indi- [12]ZHOU Tao,Lu Linyuan,ZHANG Yicheng.Predicting viduals in social networks[J].The journal of mathematical missing links via local information [J].The European s0 ciology,1971,1(1):49-80. physical journal B,2009,71(4):623-630 [25]XIE Yanbo,ZHOU Tao,WANG Binghong.Scale-free net- [13]CLAUSET A,MOORE C,NEWMAN M E J.Hierarchical works without growth[J].Physica A:statistical mechanics structure and the prediction of missing links in networks and its applications,2008,387(7):1683-1688. [J].Nature,2008,453(7191):98-101. [26]Lii Linyuan,JIN Cihang,ZHOU Tao.Similarity index [14]GUIMERa R,SALES-PARDO M.Missing and spurious in- based on local paths for link prediction of complex net- teractions and the reconstruction of complex networks[J]. works[J].Physical review E.2009.80(4):046122. Proceedings of the national academy of sciences of the U. [27]KATZ L.A new status index derived from sociometric anal- nited States of America,2009,106(52):22073-22078. ysis[J].Psychometrika,1953,18(1):39-43. [15]ADAMIC L A,HUBERMAN B A.Power-law distribution [28]BRIN S,PAGE L.The anatomy of a large-scale hypertex- of the world wide web[J].Science,2000,287(5461): tual Web search engine[J].Computer networks and ISDN 2115. systems,1998,30(1):107-117. [16]NEWMAN M E J.The structure of scientific collaboration 作者简介： networks[J].Proceedings of the national academy of sci- 张学龙.男，1978年生，副教授.博 ences of the United States of America.2001,98(2):404 士，主要研究方向为供应链管理、工业 -409. 工程，决策分析。 [17]ALBERT R,BARABGSI A L.Statistical mechanics of complex networks[J].Reviews of modern physics,2002, 74(1):47-97. [18]DOROGOVTSEV S N,MENDES J FF.Evolution of net- 王军进，男，1990年生，硕士研究 works[J].Advances in physics,2002,51(4):1079- 生，主要研究方向为供应链管理。 1187. [19]BARABOSI A L,Albert R.Emergence of scaling in ran- dom networks[J].Science,1999,286(5439):509-512.Ｌü Ｌｉｎｙｕａｎ． Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒ⁃ ｎａｌ ｏｆ ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｅｌｅｃｔｒｏｎｉｃ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉ⁃ ｎａ， ２０１０， ３９（５）： ６５１－６６１． ［９］ Ｌü Ｌｉｎｙｕａｎ， ＺＨＯＵ Ｔａｏ． Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔ⁃ ｗｏｒｋｓ： ａ ｓｕｒｖｅｙ［ Ｊ］． Ｐｈｙｓｉｃａ Ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ３９０（６）： １１５０－１１７０． ［１０］ ＧＥＴＯＯＲ Ｌ， ＤＩＥＨＬ Ｃ Ｐ． Ｌｉｎｋ ｍｉｎｉｎｇ： ａ ｓｕｒｖｅｙ ［ Ｊ］． ＡＣＭ ＳＩＧＫＤＤ ｅｘｐｌｏｒａｔｉｏｎｓ ｎｅｗｓｌｅｔｔｅｒ， ２００５， ７（２）： ３－ １２． ［１１］ＬＩＢＥＮ⁃ＮＯＷＥＬＬ Ｄ， ＫＬＥＩＮＢＥＲＧ Ｊ． Ｔｈｅ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｐｒｏｂｌｅｍ ｆｏｒ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｍｅｒｉｃａｎ ｓｏｃｉｅｔｙ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２００７， ５８ （７）： １０１９－１０３１． ［１２］ ＺＨＯＵ Ｔａｏ， Ｌü Ｌｉｎｙｕａｎ， ＺＨＡＮＧ Ｙｉｃｈｅｎｇ． Ｐｒｅｄｉｃｔｉｎｇ ｍｉｓｓｉｎｇ ｌｉｎｋｓ ｖｉａ ｌｏｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ［ Ｊ ］． Ｔｈｅ Ｅｕｒｏｐｅａｎ ｐｈｙｓｉｃａｌ ｊｏｕｒｎａｌ Ｂ， ２００９， ７１（４）： ６２３－６３０． ［１３］ＣＬＡＵＳＥＴ Ａ， ＭＯＯＲＥ Ｃ， ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｍｉｓｓｉｎｇ ｌｉｎｋｓ ｉｎ ｎｅｔｗｏｒｋｓ ［Ｊ］． Ｎａｔｕｒｅ， ２００８， ４５３（７１９１）： ９８－１０１． ［１４］ＧＵＩＭＥＲà Ｒ， ＳＡＬＥＳ⁃ＰＡＲＤＯ Ｍ． Ｍｉｓｓｉｎｇ ａｎｄ ｓｐｕｒｉｏｕｓ ｉｎ⁃ ｔｅｒａｃｔｉｏｎｓ ａｎｄ ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ Ｕ⁃ ｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， ２００９， １０６（５２）： ２２０７３－２２０７８． ［１５］ＡＤＡＭＩＣ Ｌ Ａ， ＨＵＢＥＲＭＡＮ Ｂ Ａ． Ｐｏｗｅｒ⁃ｌａｗ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｔｈｅ ｗｏｒｌｄ ｗｉｄｅ ｗｅｂ［ Ｊ］． Ｓｃｉｅｎｃｅ， ２０００， ２８７（ ５４６１）： ２１１５． ［１６］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｓｃｉｅｎｔｉｆｉｃ ｃｏｌｌａｂｏｒａｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉ⁃ ｅｎｃｅｓ ｏｆ ｔｈｅ Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， ２００１， ９８（２）： ４０４ －４０９． ［１７］ ＡＬＢＥＲＴ Ｒ， ＢＡＲＡＢáＳＩ Ａ Ｌ． Ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｒｅｖｉｅｗｓ ｏｆ ｍｏｄｅｒｎ ｐｈｙｓｉｃｓ， ２００２， ７４（１）： ４７－９７． ［１８］ＤＯＲＯＧＯＶＴＳＥＶ Ｓ Ｎ， ＭＥＮＤＥＳ Ｊ Ｆ Ｆ． Ｅｖｏｌｕｔｉｏｎ ｏｆ ｎｅｔ⁃ ｗｏｒｋｓ［ Ｊ］． Ａｄｖａｎｃｅｓ ｉｎ ｐｈｙｓｉｃｓ， ２００２， ５１ （ ４）： １０７９ － １１８７． ［１９］ＢＡＲＡＢáＳＩ Ａ Ｌ， Ａｌｂｅｒｔ Ｒ． Ｅｍｅｒｇｅｎｃｅ ｏｆ ｓｃａｌｉｎｇ ｉｎ ｒａｎ⁃ ｄｏｍ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｓｃｉｅｎｃｅ， １９９９， ２８６（５４３９）： ５０９－５１２． ［２０］ＨＡＮＬＥＹ Ｊ Ａ， ＭＣＮＥＩＬ Ｂ Ｊ． Ｔｈｅ ｍｅａｎｉｎｇ ａｎｄ ｕｓｅ ｏｆ ｔｈｅ ａｒｅａ ｕｎｄｅｒ ａ ｒｅｃｅｉｖｅｒ ｏｐｅｒａｔｉｎｇ ｃｈａｒａｃｔｅｒｉｓｔｉｃ （ＲＯＣ） ｃｕｒｖｅ ［Ｊ］． Ｒａｄｉｏｌｏｇｙ， １９８２， １４３（１）： ２９－３６． ［２１］ ＨＥＲＬＯＣＫＥＲ Ｊ Ｌ， ＫＯＮＳＴＡＮ Ｊ Ａ， ＴＥＲＶＥＥＮ Ｌ Ｇ， ｅｔ ａｌ． Ｅｖａｌｕａｔｉｎｇ ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ｒｅｃｏｍｍｅｎｄｅｒ ｓｙｓｔｅｍｓ ［Ｊ］． ＡＣＭ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ， ２００４， ２２ （１）： ５－５３． ［２２］ＺＨＯＵ Ｔａｏ， ＲＥＮ Ｊｉｅ， ＭＥＤＯ Ｍ， ｅｔ ａｌ． Ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ ｐｒｏｊｅｃｔｉｏｎ ａｎｄ ｐｅｒｓｏｎａｌ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅ⁃ ｖｉｅｗ Ｅ， ２００７， ７６（４）： ０４６１１５． ［２３］ＦＡＷＣＥＴＴ Ｔ． Ａｎ ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ＲＯＣ ａｎａｌｙｓｉｓ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｌｅｔｔｅｒｓ， ２００６， ２７（８）： ８６１－８７４． ［２４］ＬＯＲＲＡＩＮ Ｆ， ＷＨＩＴＥ Ｈ Ｃ． Ｓｔｒｕｃｔｕｒａｌ ｅｑｕｉｖａｌｅｎｃｅ ｏｆ ｉｎｄｉ⁃ ｖｉｄｕａｌｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ ｍａｔｈｅｍａｔｉｃａｌ ｓｏｃｉｏｌｏｇｙ， １９７１， １（１）： ４９－８０． ［２５］ＸＩＥ Ｙａｎｂｏ， ＺＨＯＵ Ｔａｏ， ＷＡＮＧ Ｂｉｎｇｈｏｎｇ． Ｓｃａｌｅ⁃ｆｒｅｅ ｎｅｔ⁃ ｗｏｒｋｓ ｗｉｔｈｏｕｔ ｇｒｏｗｔｈ［Ｊ］． Ｐｈｙｓｉｃａ Ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２００８， ３８７（７）： １６８３－１６８８． ［２６］ Ｌü Ｌｉｎｙｕａｎ， ＪＩＮ Ｃｉｈａｎｇ， ＺＨＯＵ Ｔａｏ． Ｓｉｍｉｌａｒｉｔｙ ｉｎｄｅｘ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｐａｔｈｓ ｆｏｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔ⁃ ｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００９， ８０（４）： ０４６１２２． ［２７］ＫＡＴＺ Ｌ． Ａ ｎｅｗ ｓｔａｔｕｓ ｉｎｄｅｘ ｄｅｒｉｖｅｄ ｆｒｏｍ ｓｏｃｉｏｍｅｔｒｉｃ ａｎａｌ⁃ ｙｓｉｓ［Ｊ］． Ｐｓｙｃｈｏｍｅｔｒｉｋａ， １９５３， １８（１）： ３９－４３． ［２８］ＢＲＩＮ Ｓ， ＰＡＧＥ Ｌ． Ｔｈｅ ａｎａｔｏｍｙ ｏｆ ａ ｌａｒｇｅ⁃ｓｃａｌｅ ｈｙｐｅｒｔｅｘ⁃ ｔｕａｌ Ｗｅｂ ｓｅａｒｃｈ ｅｎｇｉｎｅ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｎｅｔｗｏｒｋｓ ａｎｄ ＩＳＤＮ ｓｙｓｔｅｍｓ， １９９８， ３０（１）： １０７－１１７． 作者简介： 张学龙，男，１９７８ 年生，副教授，博 士，主要研究方向为供应链管理、工业 工程、决策分析。 王军进，男，１９９０ 年生，硕士研究 生，主要研究方向为供应链管理。 ·２２８· 智 能 系 统 学 报 第 １２ 卷