基于af分析复杂网络-郭军.ppt

基于激活力的复杂网络分析基于激活力的复杂网络分析 郭 军 北京邮电大学 内 容 n复杂网络研究背景 n我们所研究的问题: 网络构建及节点相似度判定 n提出的方法: 基于激活力的加权连接和亲近度测度 n实验 1: 词网建模 n实验 2: PPI 网络建模 n讨论: 脑的学习机制、特征表达、功能相似蛋白质的判定 复杂网络 n对现实世界各类复杂关系建模的有力工具 u现实世界中的复杂关系: 词间联系、蛋白质相互作用 社会关系网络、互联网节点关系、科学引用与合作关系 u网络模型: 用节点和连接表示实体之间的联系 u复杂网络(Complex networks) t大规模: 大量的节点和连接 t节点的连接通常符合 power-law 分布 t小世界模型、尺度不变性: 存在hub nodes和edge nodes 问 题 n如何根据源数据建立复杂网络模型 u源数据: 蕴含词关系的文本集、标注蛋白质相互作用关系 的数据库、蕴含用户关系的微博数据集 … n现有方法 u二值模型: 节点间的连接无权重 u缺点 t节点的关系被均匀分散在所拥有的连接上 t节点的特征不突出 t易形成连接稠密的(link-dense)网络模型 u现有的网络加权方法 tIndependent paths, betweenness centrality t基于二值网络而不是源数据进行计算 t算法极其耗时 激活力(Activation Forces) n如何对连接加权，以获得连接稀疏、节点特征突出的网络模型？ nActivation forces: 一类新统计量 u afij = (fij / fi )(fij / fj ) / dij2 tfi : 节点 i 在数据集中的出现的频度 tfij :节点 i 和节点 j在数据集中的共同出现的频度 t(fij/fi): 节点i出现条件下节点j与其共现的概率估计 t(fij/fj): 节点j出现条件下节点i与其共现的概率估计 tdij节点 i 和节点 j共现时的距离 t与万有引力公式具有同样形式 u物理意义：度量广义神经网络节 点 i 被激活后，节点 i激活节点 j 的程度 n实验表明: Activation forces 使节点的特征得到突出 u各节点的连接强度符合power-law分布 u通过删除大量的弱连接，网络的连接被稀疏化 基于激活力的亲近度(Affinity) n如何度量加权网络节点间的相似度？ n通过比较两节点所拥有连接的重合度来计算 u不同于常规的在向量空间度量的方法 nAaf 被定义为两节点入连接(in-link)和出连接(out-link)重合 度的几何平均 亲和度计算方法示意图 文本语境(context)建模 n文本语境: 任意一个文本集合 u句子、段落、文章、文本集 n现有的模型 uVSM (Vector Space Model) or BoW (Bag of Word) u特点 t文本的向量表示 t低计算复杂度 t缺少结构信息 词激活效应 n在人的头脑中存在词网，激活一个词会引发对其相关 词(有连接的词)的激活 uDoctor  nurse uDog  cat uBoy  girl uDrink  water n词激活效应在不同的领域中都得到了大量研究 u计算语言学 (computational linguistics) u认知心理学(cognitive psychologies) u认知神经科学(cognitive neural sciences) u… 词激活力(Word Activation Forces) n应用我们提出的激活力公式对词激活效应进行定量描述，获 得词激活力网络模型 n词激活力 word activation forces, 简称 wafs n将 wafs 作为个人语言经验的训练结 果 n利用大的公共文本集来近似一个普通人的语言经验 n词激活力可通过文本集中的词频和词共现频率等统计量算出 n所有词间的双向激活力构成一个有向的词网络 基于wafs对BNC建模 nBNC u英国国家文本集(The British National Corpus) u包含1亿字的有标注的多样性的英文文本 n基于词激活力对BNC建模 u取频度最高的10,000个词构成词汇表，计算词汇表中任意两词间 的激活力 uW = {wafij} i,j = 1,2,…, 10,000 uW 是包含10,000个节点的有向图 u矩阵的第i行和第 i列分别是词 i的出连接(out-link)和入连接(in- link) W的性质 n节点的入连接和出连接强度的分布符合 power law n每个词都高度选择性地分配其连接的强度 n强连接总是指向关系最密切的词 n可以删除弱连接来大幅简化网络结构，等效于对W进行 稀疏表示 W中的节点举例 由Aaf找出的关联词 n大量的词都与其最密切的关联词之间保持最高的亲近度 ua~the uability~capacity uabove~below uabroad~elsewhere uabsence~presence uabundance~diversity uabuse~violence uacademic~scientific u… 基于Aaf的词聚类 基于Aaf的词层次关系 与人工自由联想结果的比较 TargetsNeighbors of our networkAssociates of free association breadmeat cheese toastbutter dough loaf butter cream cheese flourbread margarine milk milkmeat cream winecow drink honey drinkdrinking coffee sleepwater beer thirst beerwine whisky champagnedrink wine drunk winecoffee beer champagnebeer drink dine drunkasleep alone guiltyalcohol beer drive drivedriving walk pushcar fast way walkwalking move runrun talk stroll runrunning play movewalk jog fast sleeptalk drink beddream rest awake talkspeak talking leavespeak listen chatter leavestay talk stopcome go arrive livelived stay playdie life dead playplaying played movefun ball game moveturn moved talkleave away stay ballshot match straightbat round throw throwpull pick pushball catch toss catchpick throw pullfish throw ball fish animals birds specieswater swim sea waterfood light airdrink cool wet foodmaterial water landeat drink hunger eattalk pick losefood drink fat fatsugar butter dietskinny thin cat 基于激活力的 PPI 网络建模 n选择Human Protein Reference Database (HPRD)做 源数据 u包含约3万个人类蛋白质间的3万9千个相互作用信息 u只处理拥有不少于10个相互作用关系的约5千个蛋白质 n利用激活力公式定义protein activation forces, pafs u将蛋白质相互作用关系用加权网络编码 n与词激活力网络不同，蛋白质激活力网络是无向的， 即 pafij = pafji 蛋白质激活力网络的性质 n连接的强度分布符合 power law n节点拥有连接数的分布也符合 power law uHub nodes vs. edge nodes n采用阈值1.0e-5对网络进行了连接稀疏化 n获得了一个只包含约3万条连接的稀疏网络 节点举例 癌症相关蛋白质网络 n采用所提出的亲近度测度，获得任意两个蛋白质之间的 亲近度(功能相似度) n基于这些亲近度，可以对蛋白质进行功能聚类 n令人惊喜的是: 通过设置连接数和连接强度阈值的方法， 获得了一个癌症相关蛋白质的紧凑网络 u在140个蛋白质构成的网络中，包含58个已知的癌症蛋白质 癌症相关蛋白质网络 Tp = 4; Ta = 0.03 Tp = 4; Ta = 0.04 讨 论 n词激活力可能与人脑中的词网络的形成机制有联系，隐 含的假设: u连接强度决定于词的共现概率，万有引力公式可能被用于连接强 度的定量度量 u连接可以是稀疏的，词网络的结构可以因此而避免复杂 n节点的连接结构是其特征的有效表达(模式识别的基本问题) u由于各节点的连接强度具有 power-law 的分布性质，使其特征 得到突显 n基于蛋白质激活力的功能相似蛋白质的判定方法对生物 学和医学有重要价值 谢 谢! 。