复杂网络节点相似性研究华北电力大学答辩ppt模板

复杂网络节点相似性研究及其应用华北电力大学数理系ResearchonNodesSimilarityinComplexNetworksandTheirApplication目录一二四三绪论余弦相似性指标在复杂网络社区检测中的应用余弦值相似性指标在复杂网络链路预测中的应用总结与展望2/32一绪论复杂网络简介1.1技术网络，社会网络，信息网络，生物网络数学表示：(,)GVE,1(,)0(,)ijijaij何为复杂网络（1-1）3/32-1001020304000.020.040.060.080.10.120.14KP(K)-2002040608010012000.050.10.150.20.25KP(K)图1-1随机网络及其度分布图1-2蛋白质网络度分布度与幂律性：平均路径与小世界性：聚集系数与高聚集性：ik()pkk,1(1)ijijHhnn~logHn21/201iiiiiilkkkck11niiccn其他性质：匹配性（Assortativecoefficient）度异质性（Degreeheterogeneity）网络效率（Efficiency）复杂网络中的基本概念基本性质（1-2）（1-3）（1-4）4/32复杂网络节点相似性1.2社会领域：角色对等，社交网络经济领域：推介系统信息科学领域：数据挖掘生物学领域：蛋白质功能预测复杂网络领域：社区检测，链路预测图1-3美国大学足球网络原始社区结构复杂网络节点相似性研究背景研究意义5/32节点坐标矩阵B,,1,()1,()ijijijhbij,1,2,3,iiiiinBbbbb节点坐标余弦相似性,,ijijijBBdBB优缺点：能够有效克服传统指标低估的缺点，克服大量节点之间相似性相同的缺点，但是复杂度高。二余弦相似性指标在复杂网络社区检测中的应用余弦相似性指标的定义2.1（2-1）（2-2）6/32模块度221tiiiiQeaTreeQ归一化互信息NMI值..11....112log(/)(,)log(/)log(/)ABabCCijijijijCCiijjijCCnCCTABCCnCCn社区检测结果衡量标准2.2（2-3）（2-4）7/32rk余弦阈值rd123coreSvvv,ijcorevvSdeg()irreevk,ijrdd度阈值基于核心节点的社区检测算法2.3核心节点核心节点集8/32输入：网络邻接矩阵输出：网络社区划分计算相似性矩阵和节点度数WhileWhile1提取核心节点2检测社区3计算社区划分模块度Q并记录4EndEnd找到最大模块度对应的社区划分结果minrkk1rd+0.01rrdd1rrkk算法描述minrdd9/32现实网络社区检测实验结果表2-1基于核心节点的社区检测算法实验结果网络节点数原社区数原社区模块度检测社区数检测模块度其他算法模块度Friendshipnetwork3420.371530.39440.3718（FN）footballteamnetwork115120.554110.60220.6005(GN)Dolphin’sassociationnetwork6220.275850.51840.508(BCID)Pol-booksnetwork10530.414960.5198190.51(GN)Net-sciencenetwork1589**2770.9510.927(BCID)Pol-blognetwork14902*20.4242360.4176(标签传播)10/32结论：明显提高社区检测精度和模块度值。图2-2NMI值作为Z_out的函数图像01234567890.20.30.40.50.60.70.80.91ExternaldegreeofanodeNMIBCCDFNGN11/32生成网络将该相似性矩阵的所有元素（节点相似性）变为相反数，然后再将相似性矩阵的主对角线上的元素变成原相似性矩阵各行元素的求和。1,1,21,11,12,12,2,12,1,1,2,1,1njnnjnjnnjnnnnnnjjssssssssLLssss基于余弦相似性矩阵的谱聚类算法2.4类拉普拉斯矩阵（2-5）12/32余弦值矩阵节点坐标矩阵拉普拉斯矩阵距离矩阵vsp矩阵增益矩阵特征向量空手道俱乐部网络0.64590.64590.83650.37210.02160.0101第二小0.01520.01520.00880.64590.51951最大海豚网络0.64870.64870.64870.11170.00190第二小0.0980.007400.60070.52350.5235最大特征向量第二小第二小第二小最大最大最大表2-2相似性矩阵谱平分法NMI值实验结果谱聚类实验结果元素值越小节点越相似，最大特征值对应的特征向量；元素值越大节点越相似，第二小特征值对应的特征向量13/32482311213182251167179311420102928152123161933342427302526320.050.10.150.20.250.30.350510152025303500.10.20.30.40.50.60.70.80.91NumberofcommunityNMIa空手道俱乐部网络层次树b空手道俱乐部NMI值变化曲线基于余弦相似性矩阵的层次聚类2.5层次聚类实验结果图2-3空手道俱乐部层次聚类社区检测结果14/32空手道俱乐部网络海豚交互网络政治书籍网络美国大学足球网络GN测试网络NMI10.6470.5980.9471检测社区数目222144实际社区数目2231246994757685818965788488877191689667929382867277796683737490801217095971231031261131151271001171191051101081141071091161201289811110412210211899101112124125116141511312123932281318274128176101930292726322524204825333936493843106345035545837425963406452464741454456615162536055570.040.060.080.10.120.140.160.1802040608010012000.10.20.30.40.50.60.70.80.91NumberofcommunityNMIaGN测试网络层次树bGN测试网络NMI值随社区数目变化的函数图2-4GN测试网络层次聚类社区检测结果表2-3相似性矩阵层次聚类实验结果15/32,,,,ijijijijddkldk,,1,()1,()ijijijlcij,,ijCDijijCCsCCCD指标CDI指标,=PAijijskk,,,ijCDIPAijijijCCssCCCD和CDI指标在复杂网络链路预测中的应用3.1定义（3-1）（3-2）三余弦值相似性指标在复杂网络链路预测中的应用16/32为了测试算法的准确性，将已知的连边E分为训练集ET和测试集EP两部分。在计算相似性时只能使用ET中的信息。E=ET∪EP，且ET∩EP=∅，将属于U但不属于E的边定义为不存在的边，即U-E。AUC值'0.5ttAUCtEPU-E;EP=U-EPrecision值lPrecisionL（3-3）（3-4）链路预测问题描述17/32Networksnmecrh1USAir33221260.4060.749-0.2083.462PB1224190900.3970.361-0.0793.133INT502262580.1670.033-0.1385.054Neural29721480.3080.2924-0.16321.80085Word1124250.4420.1728-0.12931.81496PPI2617118550.180.3870.4613.737NS146127420.0160.8780.4621.858Grid494165940.0630.1070.0031.459FT1156130.45040.40320.16241.0110Email113354510.29990.2540.07821.9411Jazz19827420.51320.6330.02021.3951实验数据表3-1链路预测实验数据18/32IndexINTGridWordE-mailNeuralPBPPIFTJazzUSAirNSCN0.6520.6180.6970.8600.8580.9250.9120.8330.9510.9370.979Salton0.6560.61880.6270.8540.8130.8860.9120.8460.9630.8980.979PA0.9540.5830.820.8220.7590.9090.8610.2850.7660.8860.708Sorensen0.6530.6150.6160.8540.8040.880.9170.8450.9610.9020.979LHN0.6530.6190.56110.8510.7420.7610.9080.8480.8980.7580.980CAR0.6330.6110.5530.8010.7760.9220.9150.8310.9520.9520.982RA0.6560.6150.6970.8620.8860.9300.9130.8350.9680.9550.981LP0.9470.6890.7600.9220.8730.9370.9670.8520.9430.960.993CD0.7410.9640.460.7020.6560.5040.9310.8850.9030.6070.998CD-20.960.74850.7220.940.7570.9120.9690.8480.8720.8670.998CD-30.9580.8290.6170.8810.7050.8480.9530.8430.8840.7340.999CD-60.8320.9560.4460.6840.620.4910.920.8980.8960.57550.998CDI0.970.7230.8230.8230.7930.9260.8750.410.7630.920.986链路预测实验结果表3-2链路预测实验结果19/32CD指标能够有效克服网络聚集系数低的问题CD指标对于正匹配系数网络预测效果比较好CDI指标对于负匹配系数网络预测效果比较好USAirNeuralINTWordPBGridJazzEmailFTPPINS0.30.40.50.60.70.80.91NetworkAUCCDCDIr=0图3-1CD和CDI指标在网络上的AUC值对比图实验结果分析20/32LD指标*,,,ijLDijpqpqssLD-CD指标,,,ijLDCDCDijpqpqssLD*CD指标-,,,LDCDCDCDLDijijijsss基于余弦相似性的局部紧密度链路预测算法3.2定义（3-5）（3-6）（3-7）21/32表3-3链路预测实验结果的Precision值实验结果12345678910USAirNeuralINTWordPBGridJazzE-mailFTNS(-0.208)(-0.1632)(-0.138)(-0.1293)(-0.079)-0.003-0.0202-0.0782-0.1624-0.462LHN0.01030000.00050.01210.10180.00180.39030.2429RA0.47120.09940.01950.06