基于PPIN的社交网络推荐系统

张 琳 张 进

(南京邮电大学计算机学院, 南京 210003)

基于PPIN的社交网络推荐系统

张 琳 张 进

(南京邮电大学计算机学院, 南京 210003)

为了提升海量数据下社交网络推荐系统的性能,将传统聚类方法与蛋白质网络的新特性相结合,提出了一种竞争-抑制节点模型(CINM).该模型将数据的整个处理流程分为节点重构、膜外聚类、膜内聚类及内容推荐4个部分,分别完成数据预处理、数据清洗、精度匹配与数据输出.在数据预处理过程中,通过矩阵运算,将复杂多维数据集构成的用户信息转换成结构化定量数据,并产生数据摘要.数据清理通过判断竞争值来获取用户的特征数据.在精度匹配阶段,基于蛋白质相互作用网络的相似性匹配原理获取相似性最大的一组值,并结合与用户相关联的数据项进行最终内容或关系的推荐.实验结果表明,CINM模型可以通过数据预处理和特征值竞争抑制机制较好地完成数据过滤,从而提高数据处理效率并提升最终推荐结果的精确性.

社交网络;蛋白质相互作用网络;聚类;推荐系统;大数据

随着互联网的发展,社交网络呈现出飞速发展的态势,社交网络的服务形态也随之发生着急剧变化.现在的网络呈现出一种综合发展的态势,网络中各个领域不再相互独立地存在,而社交网络作为人类社会关系在网络中的再重现更是整合了各种数据资源,包含了各种联接关系.新的发展对社交网络的服务也提出了新的要求.蛋白质相互作用网络(protein-protein interaction network,PPIN)是分析蛋白质之间复杂结构、形态之间相互作用机制的一种研究工具.PPIN通过定义蛋白质之间的相似性来确定其功能之间的联系.蛋白质属性复杂,PPIN作为复杂网络也具有小世界性与无尺度性,与社交网络存在着相似性,可以用来作为研究社交网络的工具.

在推荐系统中,聚类作为一种成熟的理论得到了广泛应用.传统聚类技术针对的单一属性在日趋复杂的社交网络中难以发挥有效作用.文献[1]针对社交网络中出现的高维复杂数据集,将高维数据映射到低维空间,采用矩阵与对应链接结构,体现了复杂数据中的内在联系,并将特征属性与其具体的内容分离,便于量化指标.文献[2]提出了一种新的分析蛋白质结构相似性的方法,并实现了将分析蛋白质结构功能向结合分析文本信息的普及,使得蛋白质分析方法可以运用于各种包含机构关系的数据库中.文献[3]阐述了基于图的聚类与蛋白质相互作用网络描述和分类方法的共同特点.文献[4]提出了一种大型社交网络中通过定义用户相似性来进行有效推荐的方法.在非单一关系的网络中,通过对比拥有共同利益和资源的用户与一般社交网络中用户之间的差别,揭示了相似性在有效推荐中的重要作用.文献[5]提出了一种推荐高品质网页内容时的核心与长期频率逆文档相关程度算法(TF-IDF).文献[6-7]对存在先验印象下的推荐系统进行了研究,并以一个图书信息推荐系统为例,证明此推荐系统的实用性.文献[8]针对推荐系统的数据稀疏与冷启动问题,结合聚类算法与Eclat算法,对用户相似性转化数据进行了深入的推荐处理.文献[9-11]分别从用户偏好、用户聚类、用户相似度出发,设计了对应的社交网络推荐系统,将具有相同属性的用户分为一组,解决了大量社会媒体的推荐问题.并以新浪微博为例,解决了弱关系下新用户冷启动的问题,提高了推荐准确率与用户满意度.

对已有数据的分类度量是一项重要工作.文献[12]提出了一种基于凝聚式聚类方法抽取网络层次结构的算法,基于拓扑结构分析,给出了社会网络的标注密度估计函数,并通过其在网络层次结构上的聚合操作,计算聚簇的特征性指标,从而发现特征聚簇.文献[13]通过改进遗传算法,减少了搜算空间,加速了算法的收敛.文献[14-15]分别提出了蛋白序列聚类方法以及利用改进蜂群算法提高蛋白质网络聚类的方法,基于复杂网络之间的相似性,可将这些算法延伸至其他领域.文献[16]通过隐式反馈处理大规模用户的习惯信息,并基于其缺少负反馈的问题设计了评价机制,从而提升了数据的训练效率.

本文以PPIN为基础,结合协同过滤技术,构建了CINM模型.在CINM模型中,大量的节点信息通过一种称为特征基因的数据摘要游走于PPIN中.网络中节点产生的数据摘要到达该网络中的一个随机节点后,与该节点的特征属性进行匹配,通过正负压竞争机制筛选出满足条件的节点,然后进入下一个聚类推荐环节,由此便可大量减少聚类过程中运算资源的开销.在推荐环节中,根据节点的优势属性结合其可能的劣势属性计算相对密度值,进而分析其与目标节点的相对吸引力,从而完成最终的推荐任务.

1 CINM框架模型

本模型在PPIN的基础上,以节点间的相似性为度量依据,确定节点的关联性.在关联性到达设定要求的情况下,对节点所含数据进行聚类运算,根据聚类结果进行推荐,从而对社交网络中的实时和高维复杂的数据进行高效准确的处理.模型示意图如图1所示.

图1 CINM模型示意图

CINM模型将数据的整个处理流程分为节点重构、膜外聚类、膜内聚类、内容推荐4个部分.

1) 节点重构.构建适应CINM模型的节点数据,包含外部竞争通道、免疫机制、内部密度控制与核心表达结构.

2) 膜外聚类.节点重构后产生的特征基因游走于PPIN中,遇到匹配节点时尝试通过外部竞争通道,目的是对大量数据源进行预处理,将相似度不合要求的数据源先期排除,减少了聚类的开销.

3) 膜内聚类.对于已经通过了竞争通道并且没有触发免疫机制的源数据,进行密度换算,并与待匹配节点的密度进行对比,从而决定最终的待推荐目标.

4) 内容推荐.从待推荐目标中分析用户可能的潜在社会关系、潜在兴趣以及感兴趣的内容.

2 算法

2.1 节点重构

社交网络中的节点对应着现实生活中的人.众所周知,人具有复杂的属性,故其在社交网络中的活动无法仅由一个表示相对位置与结构关联的纯节点表示.社交网络中的各种操作都包含了复杂数据,由这些复杂数据组成的多维数据集对进行相似节点的聚类造成了很大的干扰,并提升了聚类的难度.因此,在进行具体聚类操作前,对多维数据集进行数据预处理是有必要的.另外,为了完成针对性的推荐,应避免数据的过分扎堆聚集,即聚类结果应尽量是离散的.

CINM模型仿细胞结构包括外部竞争通道、免疫机制、内部密度控制与核心表达4个模块.

外部竞争通道的作用是进行聚类前的数据预处理,通过设置竞争通道来实现数据壁垒的功能,过滤掉关联性低于设定值的数据源及无关数据.

免疫机制与竞争通道相辅相成,用户作为社交网络的主体,对内容有着天然的好恶特征,故对于包含有抗原的数据源进行选择性过滤.

内部密度控制是对已经通过了竞争通道的数据,在进行聚类运算时根据待匹配节点的状态由膜内聚类算法控制其密度,进而控制其向待匹配节点靠拢的速度.

核心表达功能与外部竞争通道相配合,通过摘要算法产生一个特征基因数据包,该数据包进入PPIN进行传播,与其他节点的竞争通道进行匹配.

2.2 膜外聚类

CINM节点产生的特征基因数据包在PPIN中随机游走,到达一个CINM节点时尝试穿越竞争通道.特征基因数据包是通过CINM核心表达机制产生的一组数据摘要,包含了对应节点的基本数据内容,由一个m×n矩阵G=(fij)m×n组成,其中fij为用户的特征表达值(非负).

用户的数据类型由核心表达机制产生的一组数据摘要组成,即矩阵G的每一列代表用户的一类特征,每一行代表该列所代表特征的具体数值.由于每个节点都采用CINM结构,故产生的数据摘要在结构上是一致的,不同之处在于矩阵中代表属性的特征值存在差异.

xt,i≠0; xp,i≠0; fij≥∂

由现实关系易知,人与人之间存在较多共同点,但因为在某些敏感信息方面存在不同看法,故无法成为朋友关系.在膜外聚类阶段引入免疫机制,若αt中存在某一特定的特征值列与αp中预先设定的触发机制吻合,则忽略竞争电压φ的作用,直接对其进行过滤.

2.3 膜内聚类

通过了竞争通道的特征基因进入结构内部后,源节点与待匹配节点具有一定的相似性.在PPIN中存在大量的源节点,故在一个持续的时间段内,会有持续不断的数据摘要通过CINM结构的竞争通道.对于不断刷新的数据,一次聚类只能完成有限的推荐,匹配节点本身的特征属性不断发生改变,不同时间段通过竞争通道的特征基因具有不同的特性,推荐效果具有实时性.根据用户近一段时间的兴趣取向,进行针对性的内容与关系推荐,由此引入了一种密度控制概念的增量聚类方法.

密度控制的增量聚类方法是指按照数据类型对与匹配节点具有一定程度相似性的节点数据赋予一定的权值,然后采用密度换算算法将数据的权值与待匹配节点的权值进行密度换算.密度大于匹配节点的节点数据下沉并聚集到核心周围;密度相同的保持平衡;密度小于匹配节点的节点数据上升并远离核心.由此便可通过密度控制算法将一个时间段内最符合条件的节点聚集到核心附近,而相似度、关联度小的节点则按其密度值漂浮在核心周围,呈现出明显的离散型变化.

D中的元素为fij所代表属性的具体元素值,每一个相同的元素可以提供v的密度奖励.每一个强势属性提供V的密度奖励,每一个弱势属性提供V的密度惩罚.那么,强势属性中总的密度奖励为V+nv,弱势属性中总的密度奖励为nv-V.在整个节点范围内,所获得的密度奖励为ns(nv+V)-nw(nv-V),其中,ns表示具有竞争属性的数据列向量,nw表示具有抑制属性的数据列向量.源节点的密度可表示为

推荐节点筛选的算法步骤如下:

① 对每个已通过了入膜运算筛选的节点,选出强势属性值及弱势属性值fs,i∩fw,i;

② 在G=(fij)m×n中选出[fs,i∩fw,i]的值;

③ 比较Dt∨Dp;

⑤ 计算ρp;

⑥ 计算ρt/ρp;

⑦ 在ρt/ρp中聚类;

⑧ 得到聚类结果.

3 实验分析

实验过程中通过选取随机函数来获得用户属性值,在随机数据的基础上获取摘要矩阵,并构建索引结构,最大限度地逼近真实的使用环境.实验机器为Intel Core2双核 2GRAM Windows XP系统.

3.1 数据预处理效率

协同过滤(CF)是一种比较成熟的推荐方法,本文选取其作为比较对象.CINM的特征值取为15,可以作为稀疏矩阵处理.CF采用m×n的矩阵来表示用户对物品的喜好情况,打分越高则表示越喜欢该物品,0表示没有买过该物品.二者数据过滤效率比较结果见图2.由图可知,与CF相比,CINM可以更有效地处理数据,选出较合理的节点,从而有利于提高推荐的准确率.

图2 数据过滤效率对比图

3.2 时效对比

在整个处理过程中,CINM的时间效率对整个模型的可行性会产生重要影响.由于量化后的特征矩阵与纯文本信息的处理具有一致性,在时间效率上具有可比性,本文选取文献[5]中的TF-IDF作为比较对象.二者的时效性比较结果如图3所示.

图3 时效性比较

由图3可知,CINM的时间开销随着节点总数的增大而缓慢增大.鉴于随机数据的不确定性,算法的时间开销出现一定波动,并非严格的线性关系,而是一种带波动的上升趋势,且随着节点总数的增多,时间开销总体上处于合理的增长范围内.相比IF-IDF,CINM在时间上具有明显优势.

4 结论

1) 节点重构模块借助矩阵运算，将不同类型的数据进行统一的量化处理，变成具有膜结构与特征基因的数据节点，从而达到了数据预处理的目的.

2) 膜外聚类模块借助了蛋白质相互作用网络中的蛋白质间功能匹配方法，以相似性为依据，能够过滤噪声节点并通过引入免疫机制，从而提高了推荐系统的准确率.

3) 膜内聚类模块将经过预处理和清洗操作的数据进行密度换算，通过与待匹配节点进行对比，选择出待推荐节点，并交给内容推荐模块，完成最终的推荐，从而提高了推荐结果的高效性.

References)

[1]Altingovde I S, Subakan Ö N, Ulusoy Ö. Cluster searching strategies for collaborative recommendation systems[J].InformationProcessing&Management, 2013, 49(3): 688-697. DOI:10.1016/j.ipm.2012.07.008.

[2]Franceschini A, Szklarczyk D, Frankild S, et al. STRING v9.1: Protein-protein interaction networks, with increased coverage and integration[J].NucleicAcidsRes, 2013, 41(D1): D808-D815. DOI:10.1093/nar/gks1094.

[3]Pizzuti C, Rombo S E, Marchiori E. Complex detection in protein-protein interaction networks: A compact overview for researchers and practitioners [C]//10thEuropeanConferenceonEvolutionaryComputation,MachineLearningandDataMininginBioinformatics. Málaga, Spain, 2012: 211-223. DOI:10.1007/978-3-642-29066-4_19.

[4]de Meo P, Nocera A, Terracina G, et al. Recommendation of similar users, resources and social networks in a Social Internetworking Scenario[J].InformationSciences, 2011, 181(7): 1285-1305. DOI:10.1016/j.ins.2010.12.001.

[5]Sohn J S, Bae U B, Chung I J. Contents recommendation method using social network analysis[J].WirelessPersonalCommunications, 2013, 73(4): 1529-1546. DOI:10.1007/s11277-013-1264-z.

[6]Kempe D, Kleinberg J, Tardos É. Influential nodes in a diffusion model for social networks[C]//InternationalColloquiumonAutomata,LanguagesandProgramming. Lisbon, Portugal, 2005: 1127-1138. DOI:10.1007/11523468_91.

[7]Leem B, Chun H. An impact of online recommendation network on demand[J].ExpertSystemswithApplications, 2014, 41(4): 1723-1729. DOI:10.1016/j.eswa.2013.08.071.

[8]Pandya S, Shah J, Joshi N, et al. A novel hybrid based recommendation system based on clustering and association mining[C]//10thInternationalConferenceonSensingTechnology. Nanjing, China, 2016: 1-6. DOI:10.1109/icsenst.2016.7796287.

[9]贾大文,曾承,彭智勇,等.一种基于用户偏好自动分类的社会媒体共享和推荐方法[J].计算机学报,2012,35(11):2381-2391. DOI:10.3724/SP.J.1016.2012.02381. Jia Dawen, Zeng Cheng, Peng Zhiyong, et al. A user preference based automatic potential group generation method for social media sharing and recommendation[J].ChineseJournalofComputers, 2012, 35(11): 2381-2391. DOI:10.3724/SP.J.1016.2012.02381.(in Chinese)

[10]陈克寒,韩盼盼,吴健.基于用户聚类的异构社交网络推荐算法[J].计算机学报,2013,36(2):349-359. DOI:10.3724/SP.J.1016.2013.00349. Chen Kehan, Han Panpan, Wu Jian. User clustering based social network recommendation[J].ChineseJournalofComputers, 2013, 36(2): 349-359. DOI:10.3724/SP.J.1016.2013.00349.(in Chinese)

[11]荣辉桂,火生旭,胡春华,等.基于用户相似度的协同过滤推荐算法[J].通信学报,2014(2):16-24. Rong Huigui, Huo Shengxu, Hu Chunhua, et al. User similarity-based collaborative filtering recommendation algorithm[J].CommunicationJournal, 2014(2): 16-24. (in Chinese)

[12]何东晓,周栩,王佐,等.复杂网络社区挖掘——基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170. He Dongxiao, Zhou Xu, Wang Zuo, et al. Community mining in complex networks—Clustering combination based genetic algorithm [J].ActaAutomaticaSinica, 2010, 36(8): 1160-1170. (in Chinese)

[13]韩毅,方滨兴,贾焰,等.基于密度估计的社会网络特征簇挖掘方法[J].通信学报,2012,33(5):38-48. DOI:10.3969/j.issn.1000-436X.2012.05.005. Han Yi, Fang Binxing, Jia Yan, et al. Mining characteristic clusters: a density estimation approach[J].JournalonCommunications, 2012, 33(5): 38-48. DOI:10.3969/j.issn.1000-436X.2012.05.005.(in Chinese)

[14]唐东明,朱清新,杨凡,等.一种有效的蛋白质序列聚类分析方法[J].软件学报,2011,22(8):1827-1837. DOI:10.3724/SP.J.1001.2011.03848. Tang Dongming, Zhu Qingxin, Yang Fan, et al. Efficient cluster analysis method for protein sequences[J].JournalofSoftware, 2011, 22(8): 1827-1837. DOI:10.3724/SP.J.1001.2011.03848.(in Chinese)

[15]雷秀娟,田建芳.蛋白质相互作用网络的蜂群信息流聚类模型与算法[J].计算机学报,2012,35(1):134-145. DOI:10.3724/SP.J.1016.2012.00134. Lei Xiujuan, Tian Jianfang. The information flow clustering model and algorithm based on the artificial bee colony mechanism of PPI network[J].ChineseJournalofComputers, 2012, 35(1): 134-145. DOI:10.3724/SP.J.1016.2012.00134.(in Chinese)

[16]王智圣,李琪,汪静,等.基于隐式用户反馈数据流的实时个性化推荐[J].计算机学报,2016,39(1):52-64. DOI:10.11897/SP.J.1016.2016.00052. Wang Zhisheng, Li Qi, Wang Jing, et al. Real-time personalized recommendation based on implicit user feedback data stream[J].ChineseJournalofComputers, 2016, 39(1): 52-64. DOI:10.11897/SP.J.1016.2016.00052.(in Chinese)

Social network recommendation system based on PPIN

Zhang Lin Zhang Jin

(College of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

To improve the performance of the social network recommendation system on massive data, a competition-inhibition node model (CINM) is proposed by combing the traditional clustering methods with the new features of the protein networks. The whole processing flow is divided into four parts including node reconstruction, out-of-band clustering, intra-film clustering and content recommendation, in which data preprocessing, data cleaning, precision matching and data output are performed, respectively. In data preprocessing, the user information with the complex cube is converted into the structured quantitative data by the matrix operation, and the data summary is generated. In data cleaning, the user’s characteristic data are obtained by judging the competition value. During the precision matching phase, a set of values with the greatest similarity are acquired by the similarity matching principle of the protein-protein interaction network. The final content or the relationship can be recommended by the user-association data items. The experimental results show that the CINM model can complete data filtering by data preprocessing and eigenvalue competition prefabrication mechanism to improve the efficiency of data processing and the accuracy of the final recommendation results.

social network; protein-protein interaction network; cluster; recommendation system; massive data

10.3969/j.issn.1001-0505.2017.03.011

2016-10-12. 作者简介: 张琳(1980—)，女，博士，副教授， zhangl@njupt.edu.cn.

国家自然科学基金资助项目(61373017，61402241，61472192，61572260，61572261)、江苏省科技支撑计划资助项目(BE2014718，BE2015702)、江苏省自然科学基金优秀青年基金资助项目(BK20160089)、江苏省普通高校研究生科研创新计划资助项目(CXLX12_0482)、南京邮电大学校级科研基金资助项目(NY217050).

张琳,张进.基于PPIN的社交网络推荐系统[J].东南大学学报(自然科学版),2017,47(3):478-482.

10.3969/j.issn.1001-0505.2017.03.011.

TP393

A

1001-0505(2017)03-0478-05