• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 11
    • 下载费用:30 金币  

    重庆时时彩杀跨分析图: 一种在线社交网络中朋友关系预测的方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201410025336.3

    申请日:

    2014.01.16

    公开号:

    CN103795613A

    公开日:

    2014.05.14

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):H04L 12/58申请日:20140116|||公开
    IPC分类号: H04L12/58; G06F17/30; G06Q10/04(2012.01)I 主分类号: H04L12/58
    申请人: 西北工业大学
    发明人: 郭斌; 於志文; 罗惠; 周兴社; 倪红波; 王柱
    地址: 710129 陕西省西安长安区东祥路1号
    优先权:
    专利代理机构: 代理人:
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410025336.3

    授权公告号:

    ||||||

    法律状态公告日:

    2017.02.01|||2014.06.11|||2014.05.14

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明涉及一种在线社交网络中朋友关系预测的方法,该具体过程为:基于社交网站提供的API接口采集用户在社交网络上的签到数据及朋友关系;根据采集的数据提取特征来表征用户之间的关系,选取信息增益最大的三个特征来表征用户之间的朋友关系;按城市选取社交网络中在的所有在该城市有签到数据及有签到数据的用户的朋友关系作为训练数据,将朋友关系数据和非朋友关系数据比例定为1∶3,按选取的三个特征采用分类算法建立朋友关系模型;选取要预测用户的签到和朋友关系数据作为测试数据,对选取的每个用户,预测其与测试数据中其他所有用户之间的关系。本发明使得预测效果更接近用户的客观实际情况,有效的提高朋友关系预测的正确率。

    权利要求书

    权利要求书
    1.  一种在线社交网络中朋友关系预测的方法,其特征在于,该具体过程为:
    步骤101,基于社交网站提供的API接口采集用户在社交网络上的签到数据及朋友关系;
    步骤102,根据采集的数据提取特征来表征用户之间的关系,以信息增益为标准,衡量选取特征的信息含量,选取信息增益最大的三个特征来表征用户之间的朋友关系;
    步骤103,按城市选取社交网络中在的所有在该城市有签到数据及有签到数据的用户的朋友关系作为训练数据,将朋友关系数据和非朋友关系数据比例定为1∶3,按选取的三个特征采用分类算法建立朋友关系模型;
    步骤104,选取要预测用户的签到和朋友关系数据作为测试数据,对选取的每个用户,预测其与测试数据中其他所有用户之间的关系。

    2.  根据权利要求1所述的在线社交网络中朋友关系预测的方法,其特征在于,上述步骤102中选取用户社交拓扑、用户签到地点类型和用户签到地点三个特征;上述特征的具体计算方法如下:
    定义社交网络Gs(Us,Es),节点us表示用户,假定Gs为完全图,若两用户ui,uj是朋友,则用一条朋友边连接;若他们为非朋友,则用一条非朋友边连接,当去掉用户ui,uj之间的朋友边后,他们之间即为非朋友边,非朋友边不能被删除。

    3.  根据权利要求2所述的在线社交网络中朋友关系预测的方法,其特征在于,所述用户社交网络的计算方法如下:
    在社交网Gs中,去掉社交网Gs中用户i和用户j之间的朋友边,用户i和用户j拓扑网络中的最短距离即为他们在用户拓扑网络中的社交距离;若用户之间为朋友边,则其距离为1,否则为无穷大;在计算用户i和用户j社交距离之前,若用户i和用户j之间为朋友边则先在社交网Gs中删除该边eij,若为非朋友边则直接计算;
    设用户i和用户j之间的用户边在社交网络结构中的社交距离为属性as,其计算方法如公式1所示;
    as(i,j)=shortest_dis tan ce(ui,uj)inG′s(Us,Es-eij)   (1)
    最短距离的计算方法可采用Dijkstra算法或Floyd算法。

    4.  根据权利要求2或3所述的在线社交网络中朋友关系预测的方法,其特征在于,所述用户签到地点类型的计算方法如下:
    定义用户ui签到地点类型为i,每个地点签到的次数分别为(ci1,ci2......,ciN), 总的签到次数为ci,设共有L个用户,每个用户在地点i签到的次数为(Ti1,Ti2......,TiL),定义用户k在地点tik,签到的概率为p(k);引入地点信息熵的概念,定义如公式2所示,
    E(ti)=Σi=1L-pi(k)logpi(k)---(2)]]>
    定义用户签到地点类型属性为at,用户在地点信息熵小的地方有共同签到的人更有可能成为朋友,如用户a的住宅,用户a签到的次数较多,其他用户签到次数较少,这个地点的地点信息熵小,为私密地点,若用户b也在该地点签到,则用户b很可能是用户a的朋友或者用户b成为用户a的朋友的概率更大;
    则对每个用户i和用户j,其对应的用户关系有:


    5.  根据权利要求2或3所述的在线社交网络中朋友关系预测的方法,其特征在于,用户签到地点,
    定义用户ui签到的地点序列i,每个地点签到的次数分别为(ci1,ci2......,ciN),总的签到次数为Ci,Dist(lim,ljn)表示用户i的第m个签到地点和用户j的第n个签到地点之间的距离;在距离相同时签到的次数越多成为朋友的可能性越大;如果两个用户经常签到地点相近则表明他们是邻居或在相同的地方工作,否则表明他们只是偶然碰见。

    6.  根据权利要求2所述的在线社交网络中朋友关系预测的方法,其特征在于,上述步骤101中,采集的数据有用户签到时间、签到地点及其类型、用户的朋友关系。

    7.  根据权利要求2所述的在线社交网络中朋友关系预测的方法,其特征在于,在上述步骤104中,对于要预测朋友关系的用户,选取其在社交网络上的签到时间、签到地点及其类型、用户的朋友关系;按选取的特征描述该用户与其他用户的关系,根据建立的朋友关系模型将这些特征描述的用户关系分成朋友关系与非朋友关系。

    8.  根据权利要求7所述的在线社交网络中朋友关系预测的方法,其特征在于,通过挖掘潜在的朋友关系建立朋友预测模型并进行测试验证,该具体过程为:
    在已有的社交拓扑网络中先随机删除部分朋友边,然后根据删除朋友边后的社交拓扑网络计算边的特征属性值,将删除的朋友边数据以及随机选取的部分数据作为测试数据,随机选取一定的朋友边和非朋友边数据采 用分类算法建立模型,根据模型对测试数据分类的结果检测模型挖掘社交拓扑网络中潜在朋友关系的性能。

    9.  根据权利要求7或8所述的在线社交网络中朋友关系预测的方法,其特征在于,通过交叉验证建立朋友预测模型并进行测试验证,该具体过程为:
    以一个社交拓扑网络中的数据建立模型,以另一个社交拓扑网络中的数据做测试,然后反过来以作测试的社交拓扑网络为训练数据,以训练的社交拓扑网络为测试数据。

    说明书

    说明书一种在线社交网络中朋友关系预测的方法
    技术领域
    本发明涉及社会计算技术领域,尤其涉及一种在线社交网络中朋友关系预测的方法。
    背景技术
    近年来社交网络得到了迅猛的发展,人们对信息的获取和消息的传递开始变得越来越依赖于网络,用户可以通过分享新闻、日志、视频、音乐及相片等方法,维持和开拓人际关系。在线社交网络是虚拟和现实的结合,人们在现实生活中的行为和他们在社交网络中的行为有很大程度的相似性,这些行为相似的并且在地理上相距比较近的人更有可能成为朋友。
    在线社交网络基于六度分割理论运作,即你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。这就是六度分割理论,也叫小世界理论。每个个体的社交圈不断放大,最后形成一个大型的社交拓扑网络。
    专利200610157496.9提出了一种社交网络社区的推荐朋友的方法,但其没有考虑用户的社交圈子以及用户之间的距离。专利200910213921.5只公开了社交网络中社区推荐异性朋友的方法,其只考虑了用户的特征信息,没有用户的行为信息。专利200810009403.7提出了社会网络的竞争性朋友排名的方法,强调朋友之间的互动,忽略了用户本身的行为和地域等信息。
    鉴于上述缺陷,本发明创作者经过长时间的研究和实践终于获得了本创作。
    发明内容
    本发明的目的在于提供一种在线社交网络中朋友关系预测的方法,用以克服上述技术缺陷。
    为实现上述目的,本发明提供一种在线社交网络中朋友关系预测的方 法,该具体过程为:
    步骤101,基于社交网站提供的API接口采集用户在社交网络上的签到数据及朋友关系;
    步骤102,根据采集的数据提取特征来表征用户之间的关系,以信息增益为标准,衡量选取特征的信息含量,选取信息增益最大的三个特征来表征用户之间的朋友关系;
    步骤103,按城市选取社交网络中在的所有在该城市有签到数据及有签到数据的用户的朋友关系作为训练数据,将朋友关系数据和非朋友关系数据比例定为1∶3,按选取的三个特征采用分类算法建立朋友关系模型;
    步骤104,选取要预测用户的签到和朋友关系数据作为测试数据,对选取的每个用户,预测其与测试数据中其他所有用户之间的关系。
    进一步,上述步骤102中选取用户社交拓扑、用户签到地点类型和用户签到地点三个特征;上述特征的具体计算方法如下:
    定义社交网络Gs(Us,Es),节点us表示用户,假定Gs为完全图,若两用户ui,uj是朋友,则用一条朋友边连接;若他们为非朋友,则用一条非朋友边连接,当去掉用户ui,uj之间的朋友边后,他们之间即为非朋友边,非朋友边不能被删除。
    进一步,所述用户社交网络的计算方法如下:
    在社交网Gs中,去掉社交网Gs中用户i和用户j之间的朋友边,用户i和用户j拓扑网络中的最短距离即为他们在用户拓扑网络中的社交距离;若用户之间为朋友边,则其距离为1,否则为无穷大;在计算用户i和用户j社交距离之前,若用户i和用户j之间为朋友边则先在社交网Gs中删除该边eij,若为非朋友边则直接计算;
    设用户i和用户j之间的用户边在社交网络结构中的社交距离为属性as,其计算方法如公式1所示;
    as(i,j)=shortest_dis tan ce(ui,uj)inG′s(Us,Es-eij)   (1)
    最短距离的计算方法可采用Dijkstra算法或Floyd算法。
    进一步,所述用户签到地点类型的计算方法如下:
    定义用户ui签到地点类型为i,每个地点签到的次数分别为(ci1,ci2,......,ciN),总的签到次数为ci,设共有L个用户,每个用户在地点i签到的次数为(Ti1,Ti2......,TiL),定义用户k在地点tik,签到的概率为p(k);引入地点信息熵的概念,定义如公式2所示,
    E(ti)=Σi=1L-pi(k)logpi(k)---(2)]]>
    定义用户签到地点类型属性为at,用户在地点信息熵小的地方有共同签到的人更有可能成为朋友,如用户a的住宅,用户a签到的次数较多,其他用户签到次数较少,这个地点的地点信息熵小,为私密地点,若用户b也在该地点签到,则用户b很可能是用户a的朋友或者用户b成为用户a的朋友的概率更大;
    则对每个用户i和用户j,其对应的用户关系有:

    进一步,用户签到地点,
    定义用户ui签到的地点序列i,每个地点签到的次数分别为(ci1,ci2......,ciN),总的签到次数为Ci,Dist(lim,ljn)表示用户i的第m个签到地点和用户j的第n个签到地点之间的距离;在距离相同时签到的次数越多成为朋友的可能性越大;如果两个用户经常签到地点相近则表明他们是邻居或在相同的地方工作,否则表明他们只是偶然碰见。
    进一步,上述步骤101中,采集的数据有用户签到时间、签到地点及其类型、用户的朋友关系。
    进一步,在上述步骤104中,对于要预测朋友关系的用户,选取其在社交网络上的签到时间、签到地点及其类型、用户的朋友关系;按选取的特征描述该用户与其他用户的关系,根据建立的朋友关系模型将这些特征描述的用户关系分成朋友关系与非朋友关系。
    进一步,通过挖掘潜在的朋友关系建立朋友预测模型并进行测试验证,该具体过程为:
    在已有的社交拓扑网络中先随机删除部分朋友边,然后根据删除朋友边后的社交拓扑网络计算边的特征属性值,将删除的朋友边数据以及随机选取的部分数据作为测试数据,随机选取一定的朋友边和非朋友边数据采用分类算法建立模型,根据模型对测试数据分类的结果检测模型挖掘社交拓扑网络中潜在朋友关系的性能。
    进一步,通过交叉验证建立朋友预测模型并进行测试验证,该具体过程为:
    以一个社交拓扑网络中的数据建立模型,以另一个社交拓扑网络中的数据做测试,然后反过来以作测试的社交拓扑网络为训练数据,以训练的社交拓扑网络为测试数据。
    与现有技术相比较本发明的有益效果在于:本发明提取的特征包含用户在线行为、地理特征以及用户的社交圈子,使得对用户的朋友关系进行 预测时同时考虑了用户的在线行为和离线活动,融合了线上和线下特征,使得预测效果更接近用户的客观实际情况,有效的提高朋友关系预测的正确率。
    附图说明
    图1为本发明实例中朋友关系预测的流程图;
    图2为本发明实例中对潜在的朋友关系挖掘的结果示意图;
    图3为本发明实例中交叉验证的朋友关系预测的结果示意图。
    具体实施方式
    以下结合附图,对本发明上述的和另外的技术特征和优点作更详细的说明。
    本发明在考虑用户的社交圈子,在线行为和地域等因素的基础上,给出精确的基于社交网络的朋友关系预测方法。
    请参阅图1所示,本发明在线社交网络中朋友关系的预测方法的具体过程为:
    步骤101,基于社交网站提供的API接口采集用户在社交网络上的签到数据及朋友关系;
    根据社交网站提供的API接口采集用户的签到数据,采集的数据有用户签到时间、签到地点及其类型、用户的朋友关系。
    步骤102,根据采集的数据提取特征来表征用户之间的关系,以信息增益为标准,衡量选取特征的信息含量,选取信息增益最大的三个特征来表征用户之间的朋友关系;
    以选取Foursquare中巴黎签到的用户数据为例,其中用户2731人,朋友边5590,非朋友边3722225,故目标属性(用户关系)信息熵为0.0162。选取的五个属性如表1所示??梢钥闯鲇没┑降氐愣院陀没┑酱问男畔⒃鲆嫣?,对朋友预测的影响几乎可以忽略,因此在本发明中选取三个重要属性:用户社交拓扑、用户签到地点类型和用户签到地点。
    表1不同属性的信息增益
    属性信息增益用户社交拓扑0.0055用户签到地点类型0.0021
    用户签到地点0.0012用户签到地点对0.0004用户签到数目0.0002
    根据采集的数据提取特征来表征用户之间的关系,以信息增量为标准选取上述用户社交拓扑、用户签到地点类型和用户签到地点三个特征。上述特征的具体计算方法如下:
    定义社交网络Gs(Us,Es),节点us表示用户,由现实网络中朋友关系通常是对称的可知Gs为无向图。假定Gs为完全图,若两用户ui,uj是朋友则在用一条朋友边连接,若他们为非朋友则用一条非朋友边连接。当去掉用户ui,uj之间的朋友边后,他们之间即为非朋友边,非朋友边不能被删除。
    1、用户社交拓扑
    在社交网Gs中,去掉图Gs中用户i和用户j之间的朋友边(若用户是朋友的话),用户i和用户j拓扑网络中的最短距离即为他们在用户拓扑网络中的社交距离。若用户之间为朋友边,则其距离为1,否则为无穷大。设用户i和用户j之间的用户边在社交网络结构中的社交距离为属性as,在计算用户i和用户j社交距离之前,若用户i和用户j之间为朋友边则先在社交网Gs中删除该边eij,若为非朋友边则直接计算;其计算方法如公式1所示。最短距离的计算方法可采用Dijkstra算法或Floyd算法。
    as(i,j)=shortest_dis tan ce(ui,uj)inG′s(Us,Es-eij)   (1)
    2、用户签到地点类型
    定义用户ui签到地点类型为i,每个地点签到的次数分别为(ci1,ci2......,ciN),总的签到次数为ci,设共有L个用户,每个用户在地点i签到的次数为(Ti1,Ti2......,TiL),定义用户k在地点tik,签到的概率为p(k)。引入地点信息熵的概念,定义如公式2所示。
    E(ti)=Σi=1L-pi(k)logpi(k)---(2)]]>
    定义用户签到地点类型属性为at,用户在地点信息熵小的地方有共同签到的人更有可能成为朋友,如用户a的住宅,用户a签到的次数较多,其他用户签到次数较少,这个地点的地点信息熵小,为私密地点,若用户b也在该地点签到,则用户b很可能是用户a的朋友或者用户b成为用户a的朋友的概率更大。在地点公开程度较高的地方,如公共汽车站,两个用户虽 然同时在该地方签到,但偶然性的概率非常大。本发明忽略地点信息熵大于5的地点记录。则对每个用户i和用户j,其对应的用户关系有:

    3、用户签到地点
    定义用户ui签到的地点序列i,每个地点签到的次数分别为(ci1,ci2......,ciN),总的签到次数为Ci,Dist(lim,ljn)表示用户i的第m个签到地点和用户j的第n个签到地点之间的距离,本发明认为签到距离在0.3Km以内为同一个地方。在距离相同时签到的次数越多成为朋友的可能性越大。如果两个用户经常签到地点相近则表明他们是邻居或在相同的地方工作,否则表明他们只是偶然碰见。
    步骤103,按城市选取社交网络中在的所有在该城市有签到数据及有签到数据的用户的朋友关系作为训练数据,将朋友关系数据和非朋友关系数据比例定为1∶3,按选取的三个特征采用分类算法建立朋友关系模型。
    按城市选取社交网络中在的所有在该城市有签到数据及有签到数据的用户的朋友关系作为训练数据,将朋友关系数据和非朋友关系数据比例定为1∶3,用上述的三个特征来描述用户之间的关系。
    本实施例中,分别选取Foursquare中巴黎和伦敦两个城市的数据和街旁中北京和上海两个城市的签到数据,每个城市的用户组成一个社交拓扑网络,按选取的特征来描述每个社交拓扑网络中用户之间的关系选取随机森林、SVM和朴素贝叶斯三种分类算法建立朋友关系预测模型。
    步骤104,选取要预测用户的签到和朋友关系数据作为测试数据,对选取的每个用户,预测其与测试数据中其他所有用户之间的关系。
    对于要预测朋友关系的用户,选取的他在社交网络上的签到时间、签到地点及其类型、用户的朋友关系。按选取的特征描述该用户与其他用户的关系,根据建立的朋友关系模型将这些特征描述的用户关系分成朋友关系与非朋友关系,达到朋友关系预测的目的。该部分采用两种方式来建立朋友预测模型并进行测试验证。
    1、挖掘潜在的朋友关系
    在已有的社交拓扑网络中先随机删除部分朋友边,然后根据删除朋友边后的社交拓扑网络计算边的特征属性值,将删除的朋友边数据以及随机选取的部分数据作为测试数据,随机选取一定的朋友边和非朋友边数据采用分类算法建立模型,根据模型对测试数据分类的结果检测模型挖掘社交拓扑网络中潜在朋友关系的性能。
    本实施例中,分别选取Foursquare中巴黎签到数据和街旁中上海签到数据,以当前的用户社交网络作为基准值,分别从所在的社交拓扑网络中总的朋友边数中随机删除5%和10%的朋友边,按删除朋友边后的数据计算选取的特征属性,挖掘拓扑网络中潜在用户关系。结果如图2所示。
    2、交叉验证
    采用交叉验证的方法是以一个社交拓扑网络中的数据建立模型,以另一个社交拓扑网络中的数据做测试,然后反过来以作测试的社交拓扑网络为训练数据,以训练的社交拓扑网络为测试数据。
    本实施例中,对于交叉验证,选取Foursquare中巴黎签到的数据(2731位用户)和伦敦签到数据(5665位用户);街旁上北京签到数据(3656位用户)和上海签到数据(5275位用户)进行交叉验证,将训练数据中选取的朋友边与非朋友边比例定为1∶3。实验结果如图3所示。
    本发明提取的特征包含用户在线行为、地理特征以及用户的社交圈子,使得对用户的朋友关系进行预测时同时考虑了用户的在线行为和离线活动,融合了线上和线下特征,使得预测效果更接近用户的客观实际情况,有效的提高朋友关系预测的正确率。
    以上所述仅为本发明的较佳实施例,对发明而言仅仅是说明性的,而非限制性的。本专业技术人员理解,在发明权利要求所限定的精神和范围内可对其进行许多改变,修改,甚至等效,但都将落入本发明的?;し段?。

    关 键 词:
    一种 在线 社交 网络 朋友 关系 预测 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:一种在线社交网络中朋友关系预测的方法.pdf
    链接地址://www.4mum.com.cn/p-6158691.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03