一种新型重要节点排序算法及相关复杂网络研究进展.ppt

一种新型重要节点排序算法及相关复杂网络研究进展 东北大学软件学院 任涛 大师赛排序算法 一、核心思想 最优的重要节点排序算法可使按该次序删除节点后网络最大连通子图下降得最快，即图中阴影面积最小。 本算法核心思想：基于给定的网络拓扑结构，重新添加节点，并使每次添加节点后，网络中的最大连通子图最小，进而减少最大连通子图增长的速度。 二、算法示例 6 11 2 9 12 8 7 3 4 5 10 1 原始网络，准备选择节点选择序列为{} 10 算法开始 6 11 2 9 12 7 3 4 5 10 1 选择5 序列为{5} 8 6 11 2 9 12 8 7 3 4 5 10 1 选择8 序列为{5，8} 6 11 2 9 12 8 7 3 4 10 选择1 序列为{5，8，1} 1 5 6 11 2 9 12 8 7 3 4 10 选择11 序列为{5，8，1，11} 1 5 6 11 2 9 12 8 7 3 4 10 选择9 序列为{5，8，1，11，9} 1 5 6 11 2 9 12 8 7 3 4 10 选择3 序列为{5，8，1，11，9，3} 1 5 6 11 2 9 12 8 7 3 4 10 选择10 序列为{5，8，1，11，9，3，10} 1 5 6 11 2 9 12 8 7 3 4 10 选择7 序列为{5，8，1，11，9，3，10，7} 1 5 6 11 2 9 12 8 7 3 4 10 选择4 序列为{5，8，1，11，9，3，10，7，4} 1 5 6 11 2 9 12 8 7 3 4 10 选择2 序列为{5，8，1，11，9，3，10，7，4，2} 1 5 6 11 2 9 12 7 4 5 10 1 选择6 序列为{5，8，1，11，9，3，10，7，4，2，6} 8 3 6 11 2 9 12 8 7 3 4 5 10 1 选择12 序列为{5，8，1，11，9，3，10，7，4，2，6，12} 6 11 2 9 12 8 7 3 4 5 10 1 序列为{5，8，1，11，9，3，10，7，4，2，6，12} 逆序得到{12，6，2，4，7，10，3，9，11，1，8，5} 算法结束 6 11 2 9 12 7 4 5 10 1 去除12 最大连通子图大小为9 8 3 开始去除节点 6 11 2 9 12 8 7 3 4 10 去除6 最大连通子图大小为4 1 5 6 11 2 9 12 8 7 3 4 10 1 5 去除2 最大连通子图大小为4 6 11 2 9 12 8 7 3 4 10 去除4 最大连通子图大小为2 1 5 6 11 2 9 12 8 7 3 4 10 去除7 最大连通子图大小为 2 1 5 6 11 2 9 12 8 7 3 4 10 去除10 最大连通子图大小为 2 1 5 6 11 2 9 12 8 7 3 4 10 1 5 去除3 最大连通子图大小为 1 大师赛结果值 网络 model1 model2 model3 model4 real1 real2 real3 real4 合计 鲁棒值 0.2088 0.1722 0.3627 0.1109 0.0288 0.0031 0.097 0.0394 1.0229 算法的创新点 1 从问题的评判标准（最大连通子图）出发，具有针对性。 2 通过确定节点的添加顺序，减小最大连通子图规模的增长速度。 3 每次添加节点，只需对添加矩阵进行操作，速度快，适于大规模网络。 其他研究方向介绍 音乐 纯音乐 歌曲 单一音符音乐 多音符音乐 歌词 伴奏 主旋律 基于复杂网络的音乐创作 吉他和弦生成 吉他是一种最常见的弹奏歌曲伴奏的乐器。 吉他曲谱用六线谱表示 影响因素 百分比 首音 50.4% 尾音 22.3% 出现次数最多的音 20.1% 时值最长的音 5.9% 其他 1.3% 吉他和弦生成 网络的建模 节点：和弦+对应音节的首音 边：演奏时从一个和弦到另一个和弦的连接 吉他和弦生成 主歌-副歌双层网络 主歌网络 副歌网络 吉他和弦生成 网络 采集的和弦总数 节点总数 边的总数 平均最短路径 聚类系数 邓丽君 1000 85 396 3.31 0.26 刘德华 1000 116 494 3.289 0.165 老狼 1000 79 381 2.88 0.239 齐秦 1000 136 500 3.527 0.177 Beyond 1000 71 295 2.852 0.289 张震岳 1000 95 468 3.175 0.284 小世界特性 网络的拓扑结构分析 吉他和弦生成 无标度特性 吉他和弦生成 富人俱乐部特性 吉他和弦生成 同配性 网络 同配