非流行边的预测 电子科技大学互联网科学中心 朱郁筱 yuxiao-zhu@hotmail.com Roger Kahn.

Slides:



Advertisements
Similar presentations
四川财经职业学院会计一系会计综合实训 目录 情境 1.1 企业认知 情境 1.3 日常经济业务核算 情境 1.4 产品成本核算 情境 1.5 编制报表前准备工作 情境 1.6 期末会计报表的编制 情境 1.2 建账.
Advertisements

主编:邓萌 【点按任意键进入】 【第六单元】 教育口语. 幼儿教师教育口 语概论 模块一 幼儿教师教育口语 分类训练 模块二 适应不同对象的教 育口语 模块三 《幼儿教师口语》编写组.
第一組 加減法 思澄、博軒、暐翔、寒菱. 大綱 1. 加減法本質 2. 迷思概念 3. 一 ~ 七冊分析 4. 教材特色.
海南医学院附 院妇产科教室 华少平 妊娠合并心脏病  概述  妊娠、分娩对心脏病的影响  心脏病对妊娠、分娩的影响  妊娠合病心脏病的种类  妊娠合并心脏病对胎儿的影响  诊断  防治.
植树节的由来 植树节的意义 各国的植树节 纪念中山先生 植树节的由来 历史发展到今天, “ 植树造林,绿化祖国 ” 的热潮漫卷 了中华大地。从沿海到内地,从城市到乡村,涌现了多少 造林模范,留下了多少感人的故事。婴儿出世,父母栽一 棵小白怕,盼望孩子和小树一样浴光吮露,茁壮成长;男 女成婚,新人双双植一株嫩柳,象征家庭美满,幸福久长;
客户协议书 填写样本和说明 河南省郑州市金水路 299 号浦发国际金融中 心 13 层 吉林钰鸿国创贵金属经营有 限公司.
浙江省县级公立医院改革与剖析 马 进 上海交通大学公共卫生学院
第二章 环境.
教师招聘考试 政策解读 讲师:卢建鹏
了解语文课程的基本理念,把握语文素养的构成要素。 把握语文教育的特点,特别是开放而有活力的语文课程的特点。
北台小学 构建和谐师生关系 做幸福教师 2012—2013上职工大会.
福榮街官立小學 我家孩子上小一.
第2期技職教育再造方案(草案) 教育部 101年12月12日 1 1.
企业员工心态管理培训 企业员工心态管理培训讲师:谭小琥.
历史人物的研究 ----曾国藩 组员: 乔立蓉 杜曜芳 杨慧 组长:马学思 杜志丹 史敦慧 王晶.
教育部高职高专英语类专业教学指导委员会 刘黛琳 山东 • 二○一一年八月
淡雅诗韵 七(12)班 第二组 蔡聿桐.
第七届全国英语专业院长/系主任高级论坛 汇报材料
小數怕長計, 高糖飲品要節制 瑪麗醫院營養師 張桂嫦.
制冷和空调设备运用与维修专业 全日制2+1中等职业技术专业.
会计信息分析与运用 —浙江古越龙山酒股份有限公司财务分析 组员:2006级工商企业管理专业 金国芳 叶乐慧 魏观红 徐挺挺 虞琴琴.
第六章 人体生命活动的调节 人体对外界环境的感知.
芹菜 英语051班 9号 黄秋迎 概论:芹菜是常用蔬菜之一,既可热炒,又能凉拌,深受人们喜爱。近年来诸多研究表明,这是一种具有很好药用价值的植物。 别名:旱芹、样芹菜、药芹、香芹、蒲芹 。 芹菜属于花,芽及茎类。
2012年 学生党支部书记工作交流 大连理工大学 建工学部 孟秀英
北京市职业技能鉴定管理中心试题管理科.
2014吉林市卫生局事业单位招聘153名工作人员公告解读
各類所得扣繳法令 與申報實務 財政部北區國稅局桃園分局 103年9月25日
初級游泳教學.
爱国卫生工作的持续发展 区爱卫办 俞贞龙.
第八章 数学活动 方程组图象解法和实际应用
本课内容提要 一、汇率的含义 二、汇率变化与币值的关系 三、汇率变化的影响. 本课内容提要 一、汇率的含义 二、汇率变化与币值的关系 三、汇率变化的影响.
散文鉴赏方法谈.
比亚迪集成创新模式探究 深圳大学2010届本科毕业论文答辩 姓名:卓华毅 专业:工商管理 学号: 指导老师:刘莉
如何撰写青年基金申请书 报 告 人: 吴 金 随.
点击输 入标题 点击输入说明性文字.
國際志工海外僑校服務 越南 國立臺中教育大學 2010年國際志工團隊.
痰 饮.
學分抵免原則及 學分抵免線上操作說明會.
教 学 查 房 黄宗海 南方医科大学第二临床医学院 外科学教研室.
评 建 工 作 安 排.
“十二五”国家科技计划经费管理改革培训 概预算申报与审批 国家科学技术部 2012年5月.
“十二五”国家科技计划经费管理改革培训 概预算申报与审批 国家科学技术部 2012年5月.
首都体育学院 武术与表演学院 张长念 太极拳技击运用之擒拿 首都体育学院 武术与表演学院 张长念
现行英语中考考试内容与形式的利与弊 黑龙江省教育学院 于 钢 2016, 07,黄山.
谷雨节气模板.
第5讲:比较安全学的创建 吴 超 教授 (O)
蔬果的营养及卫生 赵 中.
按開憂鬱症的結 ---穴位玄機妙用 溫嬪容 醫師.
彰化縣西勢國小備課工作坊 新生入學的班級經營 主講:黃盈禎
重庆市西永组团K标准分区基本情况介绍.
西貢區歷史文化 清水灣 鍾礎營,楊柳鈞,林顥霖, 譚咏欣,陳昭龍.
所得稅扣繳法令與實務 財政部北區國稅局桃園分局 102年12月19日 1 1.
角 色 造 型 第四章 欧式卡通造型 主讲:李娜.
走进校园流行 高二15班政治组 指导老师:曾森治老师.
医院文化建设 广东省中医院 2011年3月26日.番禺.
案例:海底捞模式 ——把服务做到极致.
医疗法律法规培训 连云港市东辛农场医院 周卫平 二0一四年十二月.
史泰博出货检验员面试中·········
09英本2班 罗芬.
个人所得税 扣缴申报表填报讲解.
主要内容 1. 利用估值对债券组合估价的优势 2. 如何评估债券估值的合理性 3. 产业债的定价与估值.
中信信诚-淮安项目.
神奇的宇宙 我们的太阳系 宇宙中天体有哪些类型? 刊号:CN77-87 编辑: 施雅苑 今日一叠4版 第1期 认识宇宙 16岁的哈勃
傷 仲 永 王安石 S 孫子潔.
「簡易水土保持申報書」 內容及送審流程之探討
实体描述呈现方法的研究 实验评估 2019/5/1.
第七、八次实验要求.
學生兼任研究助理(RA):學習與勞動型態
第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions)
105年教育部熱血老師翻轉學生「教育愛」座談會
Presentation transcript:

非流行边的预测 电子科技大学互联网科学中心 朱郁筱 yuxiao-zhu@hotmail.com Roger Kahn

问题描述 如何刻画边的流行性?(popularity) 数学角度 物理角度(乘积动力学) Roger Kahn

问题描述 为什么要考虑非流行边? 实际应用(非流行边的信息量往往更大 ) 化学反应网络 基因调控网络 网络演化的观点(网络成熟后,hub节点趋近于饱和,新出现的连边往往是非流行的) 中国航空网 Roger Kahn

基于网络结构的相似性指标 基于相似性——两个节点之间相似性越大,它们之间存在连边的可能性也就越大。分为基于节点属性的相似和基于网络结构的相似。基于网络结构的相似性指标又分为: Node-dependent Indices Common Neighbors (CN) Salton Index Jaccard Index Roger Kahn

基于网络结构的相似性指标 Sorensen Index Hub promoted Index (HPI) Hub Depressed index (HDI) Leicht-Holme-Newman-I (LHN-I) Preferencial Attachment (PA) Roger Kahn

基于网络结构的相似性指标 Path-dependent Indices Adamic-Adar (AA) Resource Allocation (RA) Path-dependent Indices Local Path (LP) :在CN的基础上考虑了三阶邻居的贡献 A:邻接矩阵 :自由参数 Roger Kahn

基于网络结构的相似性指标 Katz(考虑所有路径数,且对于短路径赋予较大的权重,对长路径赋予较小的权重) A:邻接矩阵 I : 单位阵 :权重衰减因子,为了保证数列的收敛性,要小于邻接矩阵A的最大特征值的倒数 Leicht-Holme-Newman-Ⅱ (LHN-Ⅱ) D :邻接矩阵A的度矩阵 m : 边的条数 :矩阵A的最大特征值 : 自由参数 Roger Kahn

基于网络结构的相似性指标 1)基于路径的相似性指标表现要好,但是它比基于节点的相似性指标需要的信息量多。 2)两种LHN指标的表现都不理想。 局限性:没有考虑这些指标对流行边和非流行的预测精度差别。 Roger Kahn

网络的popularity累积分布

网络的PA指数 PA指数: Random(PA): 同等规模随机网络的平均popularity M: 网络边的条数 N M C r H <d> <k> PA Datasets 332 2126 0.749 -0.206 3.46 2.46 12.807 9.923 1222 16717 0.361 -0.079 3.13 2.51 27.360 1.960 297 2148 0.308 0.454 3.47 2.46 14.456 2.512 379 941 0.798 -0.082 1.66 4.93 4.823 7.168 USAir PB Celegans NetScience

边的预测精度随popularity的变化 测试集中边的预测精度:该边的分数比网络中不存在的边分数高的概率。

边的预测精度随popularity的变化 大部分指标预测精度与边的popularity成反比。PA指标最为明显。 相对于其他指标,LHN指标的预测精度随popularity的波动不大,在某些网络中popularity小的边的预测精度反而要高些。 Roger Kahn

不同测试集时各指标的表现 数据划分: 根据原始数据计算出各边的popularity,然后对所有边按其popularity进行升序排列,并按所占比例进行5等分。分别从等分区间取出10%作为测试集。P=0.2对应的是[0, 20%]这一区间,P=1对应的是[80%, 100%]。 现象: 1、对于NS数据集,除了PA算法的预测精度与测试集中平均popularity呈正比例关系外,其他算法的预测精度都只是随P的增加有很小的波动。(NS网络的H值比较小) 2、在PB、CE、USAir三个数据集中,大部分的基于网络结构的链路预测算法的预测精度与p呈现正比例关系,尤其是PA、CN、AA、RA、LP。 3、相对于其他算法,LHN算法对popular边以及unpopular边的预测精度相差不大,有时候还会出现预测精度随P的增加还有所下降的情况。

不同测试集时各指标的表现 1、对于NS数据集,预测精度都只是随P的增加有很小的波动(PA指标除外)。(NS网络的H值比较小) 2、在PB、CE、USAir三个数据集中,大部分指标的预测精度与p呈现正比例关系,尤其是PA、CN、AA、RA、LP。 3、LHN的预测精度随p变化很小,有时候还会出现预测精度随P的增加还有所下降的情况。

Top-L-popularity Top-L-popularity: 排在前面的L条边的平均的popularity. USAir、PB、C.elegans、NetScience四个网络中,LHN-I以及LHN-Ⅱ计算出的Top-L-popularity远小于其他指标。L越小,这种差距越明显。CN、PA、AA、RA、LP、Katz的top-100-popularity远远大于LHN指标。 结论: LHN指标更倾向于预测出非流行边。

Top-L-popularity 表:基于网络结构的相似性指标(PB)

调节节点度的影响 引入自由参数a a= -1: LHN-I指标 a=-0.5:salton a=0:CN 1)最优的参数值a大体上 与P成正比 2) 测试集边比较流行时, 最优参数a很接近0. 3) 最优参数的选取对网络 的依赖性很大。

下步的工作 现有的基于相似性的指标大都更倾向于预测流行的连边。LHN指标的对非流行边的预测精度比较好。但是LHN总体上的表现又不那么令人满意,能否设计一种对流行边和非流行边预测精度都比较高的相似性指标?

THANK YOU FOR YOUR TIME Roger Kahn