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

基于激活力的复杂网络分析郭军北京邮电大学内容复杂网络研究背景我们所研究的问题:网络构建及节点相似度判定提出的方法:基于激活力的加权连接和亲近度测度实验1:词网建模实验2:PPI网络建模讨论:脑的学习机制、特征表达、功能相似蛋白质的判定复杂网络对现实世界各类复杂关系建模的有力工具现实世界中的复杂关系:词间联系、蛋白质相互作用社会关系网络、互联网节点关系、科学引用与合作关系网络模型:用节点和连接表示实体之间的联系复杂网络(Complexnetworks)大规模:大量的节点和连接节点的连接通常符合power-law分布小世界模型、尺度不变性:存在hubnodes和edgenodes问题如何根据源数据建立复杂网络模型源数据:蕴含词关系的文本集、标注蛋白质相互作用关系的数据库、蕴含用户关系的微博数据集…现有方法二值模型:节点间的连接无权重缺点节点的关系被均匀分散在所拥有的连接上节点的特征不突出易形成连接稠密的(link-dense)网络模型现有的网络加权方法Independentpaths,betweennesscentrality基于二值网络而不是源数据进行计算算法极其耗时激活力(ActivationForces)如何对连接加权，以获得连接稀疏、节点特征突出的网络模型？Activationforces:一类新统计量afij=(fij/fi)(fij/fj)/dij2fi:节点i在数据集中的出现的频度fij:节点i和节点j在数据集中的共同出现的频度(fij/fi):节点i出现条件下节点j与其共现的概率估计(fij/fj):节点j出现条件下节点i与其共现的概率估计dij节点i和节点j共现时的距离与万有引力公式具有同样形式物理意义：度量广义神经网络节点i被激活后，节点i激活节点j的程度实验表明:Activationforces使节点的特征得到突出各节点的连接强度符合power-law分布通过删除大量的弱连接，网络的连接被稀疏化基于激活力的亲近度(Affinity)如何度量加权网络节点间的相似度？通过比较两节点所拥有连接的重合度来计算不同于常规的在向量空间度量的方法Aaf被定义为两节点入连接(in-link)和出连接(out-link)重合度的几何平均1/211A[(,)(,)]||||ijijafijkikjiljlklijijORafafORafafKLKL{|00}ijkikjkaforafK{|00}ijiljllaforafL(,)(,)/(,)ORxyminxymaxxy亲和度计算方法示意图文本语境(context)建模文本语境:任意一个文本集合句子、段落、文章、文本集现有的模型VSM(VectorSpaceModel)orBoW(BagofWord)特点文本的向量表示低计算复杂度缺少结构信息词激活效应在人的头脑中存在词网，激活一个词会引发对其相关词(有连接的词)的激活DoctornurseDogcatBoygirlDrinkwater词激活效应在不同的领域中都得到了大量研究计算语言学(computationallinguistics)认知心理学(cognitivepsychologies)认知神经科学(cognitiveneuralsciences)…词激活力(WordActivationForces)应用我们提出的激活力公式对词激活效应进行定量描述，获得词激活力网络模型词激活力wordactivationforces,简称wafs将wafs作为个人语言经验的训练结果利用大的公共文本集来近似一个普通人的语言经验词激活力可通过文本集中的词频和词共现频率等统计量算出所有词间的双向激活力构成一个有向的词网络基于wafs对BNC建模BNC英国国家文本集(TheBritishNationalCorpus)包含1亿字的有标注的多样性的英文文本基于词激活力对BNC建模取频度最高的10,000个词构成词汇表，计算词汇表中任意两词间的激活力W={wafij}i,j=1,2,…,10,000W是包含10,000个节点的有向图矩阵的第i行和第i列分别是词i的出连接(out-link)和入连接(in-link)W的性质节点的入连接和出连接强度的分布符合powerlaw每个词都高度选择性地分配其连接的强度强连接总是指向关系最密切的词可以删除弱连接来大幅简化网络结构，等效于对W进行稀疏表示W中的节点举例由Aaf找出的关联词大量的词都与其最密切的关联词之间保持最高的亲近度a~theability~capacityabove~belowabroad~elsewhereabsence~presenceabundance~diversityabuse~violenceacademic~scientific…基于Aaf的词聚类基于Aaf的词层次关系与人工自由联想结果的比较TargetsNeighborsofournetworkAssociatesoffreeassociationbreadmeatcheesetoastbutterdoughloafbuttercreamcheeseflourbreadmargarinemilkmilkmeatcreamwinecowdrinkhoneydrinkdrinkingcoffeesleepwaterbeerthirstbeerwinewhiskychampagnedrinkwinedrunkwinecoffeebeerchampagnebeerdrinkdinedrunkasleepaloneguiltyalcoholbeerdrivedrivedrivingwalkpushcarfastwaywalkwalkingmoverunruntalkstrollrunrunningplaymovewalkjogfastsleeptalkdrinkbeddreamrestawaketalkspeaktalkingleavespeaklistenchatterleavestaytalkstopcomegoarrivelivelivedstayplaydielifedeadplayplayingplayedmovefunballgamemoveturnmovedtalkleaveawaystayballshotmatchstraightbatroundthrowthrowpullpickpushballcatchtosscatchpickthrowpullfishthrowballfishanimalsbirdsspecieswaterswimseawaterfoodlightairdrinkcoolwetfoodmaterialwaterlandeatdrinkhungereattalkpicklosefooddrinkfatfatsugarbutterdietskinnythincat基于激活力的PPI网络建模选择HumanProteinReferenceDatabase(HPRD)做源数据包含约3万个人类蛋白质间的3万9千个相互作用信息只处理拥有不少于10个相互作用关系的约5千个蛋白质利用激活力公式定义proteinactivationforces,pafs将蛋白质相互作用关系用加权网络编码与词激活力网络不同，蛋白质激活力网络是无向的，即pafij=pafji蛋白质激活力网络的性质连接的强度分布符合powerlaw节点拥有连接数的分布也符合powerlawHubnodesvs.edgenodes采用阈值1.0e-5对网络进行了连接稀疏化获得了一个只包含约3万条连接的稀疏网络节点举例癌症相关蛋白质网络采用所提出的亲近度测度，获得任意两个蛋白质之间的亲近度(功能相似度)基于这些亲近度，可以对蛋白质进行功能聚类令人惊喜的是:通过设置连接数和连接强度阈值的方法，获得了一个癌症相关蛋白质的紧凑网络在140个蛋白质构成的网络中，包含58个已知的癌症蛋白质癌症相关蛋白质网络Tp=4;Ta=0.03Tp=4;Ta=0.04讨论词激活力可能与人脑中的词网络的形成机制有联系，隐含的假设:连接强度决定于词的共现概率，万有引力公式可能被用于连接强度的定量度量连接可以是稀疏的，词网络的结构可以因此而避免复杂节点的连接结构是其特征的有效表达(模式识别的基本问题)由于各节点的连接强度具有power-law的分布性质，使其特征得到突显基于蛋白质激活力的功能相似蛋白质的判定方法对生物学和医学有重要价值谢谢!