掌桥科研：一站式科研服务平台 (19)中华人民共和国国家知识产权局(10 )申请公布号 CN 108765179 A( 43 )申请公布日 2018.11.06(12)发明专利申请( 21 )申请号 201810385952 .8( 22)申请日 2018 .04 .26(71 )申请人 恒安嘉新（北京）科技股份公司地址 100191 北京市海淀区北三环西路25 号27号楼五层5002室(72)发明人 庞韶敏于芳名万腾峰 黄煜恒闭雨哲杨振新王嘉康 金红刘长永杨满智蔡琳(74 )专利代理机构 北京市万慧达律师事务所11111代理人 黄玉东( 51 )Int .Cl .G06Q50/00( 2012 .01 )G06Q10/06( 2012 .01 )G06F17/30( 2006 .01 )权利要求书1页 说明书6页 附图2页( 54 )发明名称一种基于图计算的可信社交关系分析方法( 57 )摘要CN 108765179 A本发明公开了一种基于图计算的可信社交关系分析方法，所述方法包括：搜集社交网络原始数据，建立图计算模型；采用社区检测算法将所述图计算模型分成若干子图社区，并计算子图社区结点的大小；根据图计算模型，计算每个结点包含三角计数、入度、出度在内的属性特征，并结合子图社区结点大小，判断并筛选出该社交网络中为可信社交关系的用户名单。本发明可以对社交网络中的可信关系进行识别检测，并得出有效的可信社交关系。掌桥科研官网拥有中外文期刊、会议、学位、报告、专利等文献超3亿篇，以及查收、查引、查重、翻译等多种服务掌桥科研：一站式科研服务平台 CN 108765179 A权利要求书1/1 页1 .一种基于图计算的可信社交关系分析方法，其特征在于，所述方法包括： 步骤S1，搜集社交网络原始数据，建立图计算模型；步骤S2，采用社区检测算法将所述图计算模型分成若干子图社区，并计算子图社区结点的大小；步骤S3，根据图计算模型，计算每个结点包含三角计数、入度、出度在内的属性特征，并结合子图社区结点大小，判断并筛选出该社交网络中为可信社交关系的用户名单。2. .如权利要求1所述的可信社交关系分析方法，其特征在于，所述步骤S1中，建立图计算模型的过程具体包括：根据用户之间是否存在直接的社交联系，将不同的用户分成发起方用户和接收方用户，每个用户分别作为一个结点；当发起方用户至接收方用户建立社交联系时，建立从发起方用户所在的结点指向接收方用户所在结点的的一条有向边；根据建立的多个有向边，构建呈网络结构分布的所述图计算模型。3. .如权利要求2所述的可信社交关系分析方法，其特征在于，分成若干子图社区的过程具体包括如下：计算该社交网络中所有边的介数；找到介数最大的边，将其从网络中移除；重复计算该社交网络中剩余边的介数，最后当达到最大迭代次数时，算法停止。4 .如权利要求2所述的可信社交关系分析方法，其特征在于，在所述步骤S3中，判断并筛选出该社交网络中为可信社交关系的用户名单具体包括：根据计算的结点的属性特征及结点数量，计算该子图社区的相关系数，并判断相关系数是否大于设定的阈值，如低于设定的阈值，则判定为可信的社交关系，如否，则丢弃。5. .如权利要求1所述的可信社交关系分析方法，其特征在于，在所述步骤S1中，还包括对搜集的社交网络原始数据进行数据清洗和过滤，筛选出有效字段信息。6. .如权利要求4所述的可信社交关系分析方法，其特征在于，所述相关系数的计算方法为：根据熵值法确定社区中的四个属性分别对应的权重，；将入度与三角形个数、出度与三角形个数、社区结点与三角形个数分别利用皮尔逊公式求得相关系数；最后的相关系数为R(+)*corr(inDeg ,TriC)+(+)*corr(outDeg , TriC)+(+)*corr(CommVerC ,TriC) ，其中，inDeg表示入度，TriC表示三角个数，outDeg表示出度，CommVerC表示社区结点。7 .如权利要求1所述的可信社交关系分析方法，其特征在于，所述社区检测算法为GN算法。28 .如权利要求1所述的可信社交关系分析方法，其特征在于，所述社交网络原始数据包括：用户的通话数据。2掌桥科研官网拥有中外文期刊、会议、学位、报告、专利等文献超3亿篇，以及查收、查引、查重、翻译等多种服务掌桥科研：一站式科研服务平台 说明书CN 108765179 A3/6 页一种基于图计算的可信社交关系分析方法技术领域0001 本发明属于网络安全及互联网大数据领域，更具体来说，涉及一种基于图计算的可信社交关系分析方法。背景技术0002 近年来，可信关系模型越来越重要。商家、企业或者政府可以通过信用度限制个体或者群体的行为。通过社交网络可以识别某个人的信用度。可信关系还可以用于银行的风险控制系统中。众所周知，传统银行评估模型无法给过去没有发生过借贷交易的人进行信用评分，造成“无记录”的借款人风险无法评估。但是通过分析当前用户的社交关系可以有目的的构建全新的信用体系，帮助金融机构“识别”更多的信用度较高的借贷人。0003再者，近年来利用电话进行的诈骗方式呈爆发趋势，受骗面广，金额巨大，通信诈骗成为巨大的用户痛点。电信诈骗案件频发，诈骗者拥有多样的诈骗手段，让人防不胜防， 社会影响恶劣，在甄别诈骗电话时，需要进行仿冒领导、仿冒公检法、仿冒熟人、骚扰等判断，算法执行时间较长，无法有效、快捷的分析出诈骗电话号码。0004伴随着信息社会的发展，安全逐渐成为人们不可忽视的方面。从社交网络的角度看，例如社交网络中平台安全性、谣言扩散、群体性事件的产生和传播以及电信诈骗事件频繁发生，给个人，企业甚至是国家都造成了一定的伤害。对于这些问题，可以采用相应手段筛选并冻结非法用户，但对于所有的用户都进行筛选过滤显然没有必要，且随着数据量增大，系统的负担也随之增加。如果将合法用户建立库表，当采集到数据时，优先判断是否为可信社交关系库中的用户，如果是，则无需进一步识别其非法身份，这样更节省算法时间， 提高系统效率。所以研究可信社交关系有一定的现实意义和应用价值。而如果采用可信社交关系来证明用户的合法性，则可以免去复杂的判断非法身份验证步骤。发明内容0005本发明的目的是，提供一种基于图计算的可信社交关系分析方法，以解决原有的方法无法快捷有效的证明用户的可信性和合法性。0006为解决上述技术问题，本发明所采用的技术方案如下：0007一种基于图计算的可信社交关系分析方法，所述方法包括：0008步骤S1，搜集社交网络原始数据，建立图计算模型；0009步骤S2，采用社区检测算法将所述图计算模型分成若干子图社区，并计算子图社区结点的大小；0010步骤S3，根据图计算模型，计算每个结点包含三角计数、入度、出度在内的属性特征，并结合子图社区结点大小，判断并筛选出该社交网络中为可信社交关系的用户名单。0011进一步地，所述步骤S1中，建立图计算模型的过程具体包括：30012根据用户之间是否存在直接的社交联系，将不同的用户分成发起方用户和接收方用户，每个用户分别作为一个结点；3掌桥科研官网拥有中外文期刊、会议、学位、报告、专利等文献超3亿篇，以及查收、查引、查重、翻译等多种服务掌桥科研：一站式科研服务平台 说明书CN 108765179 A4/6 页0013 当发起方用户至接收方用户建立社交联系时，建立从发起方用户所在的结点至接收方用户所在结点的的一条有向边；0014根据建立的多个有向边，构建呈网络结构分布的所述图计算模型。0015进一步地，分成若干子图社区的过程具体包括如下：0016计算该社交网络中所有边的介数；0017找到介数最大的边，将其从网络中移除；0018重复计算该社交网络中剩余边的介数，最后当达到最大迭代次数时，算法停止。0019进一步地，在所述步骤S3中，判断并筛选出该社交网络中为可信社交关系的用户名单具体包括：0020 根据计算的结点的属性特征及结点数量，计算该子图社区的相关系数，并判断相关系数是否大于设定的阈值，如低于设定的阈值，则判定为可信的社交关系，如否，则丢弃。0021 进一步地，在所述步骤S1中，还包括对搜集的社交网络原始数据进行数据清洗和过滤，筛选出有效字段信息。0022进一步地，所述相关系数的计算方法为：0023根据熵值法确定社区中的四个属性分别对应的权重，；0024将入度与三角形个数、出度与三角形个数、社区结点与三角形个数分别利用皮尔逊公式求得相关系数；最后的相关系数为R (+)*corr(inDeg ,TriC)+ (+)*corr (outDeg ,TriC)+(+)*corr(CommVerC ,TriC) ，其中，inDeg表示入度，TriC表示三角个数， outDeg表示出度，CommVerC表示社区结点。0025进一步地，所述社区检测算法为GN算法。0026进一步地，所述社交网络原始数据包括：用户的通话数据。0027与现有技术相比，本发明所述的分析方法，基于图计算技术，将社交网络转化成有向图，首先根据社区检测算法将图划分成社区，根据有向图中结点的相互关系，计算每个结点的三角计数、入度、出度、社区内结点个数等作为结点属性值。根据相关系数，找出社会网络关系中的可信社交关系，也称作“白名单”。该方法能够在社交网络中识别可信度较高的用户，帮助企业、商家和政府等机构做分析、决策，共同维护社交网络的安全和用户的利益。附图说明0028图1为本发明实施例所述的基于图计算的可信社交关系分析方法的原理示意图。0029图2为本发明一个具体实施例所述的基于图计算的可信社交关系分析方法的具体步骤示意图。0030图3(a)为本发明实施例所述的呈放射状的社交网络示意图。0031图3(b)为本发明实施例所述的呈三角形的社交网络示意图具体实施方式0032以下结合附图对本发明作进一步详细说明，但不作为对本发明的限定。40033目前的可信关系的区分多种多样，大多时应用强规则认定某些群体的熟人关系， 但是这样忽略了用户之间的交互信息和用户之间所在的社区信息，甚至将通话多次的快递送餐人员也认定是熟人关系。且正常的用户行为是多变的，难以定义，很难通过一般的特征4掌桥科研官网拥有中外文期刊、会议、学位、报告、专利等文献超3亿篇，以及查收、查引、查重、翻译等多种服务掌桥科研：一站式科研服务平台 说明书CN 108765179 A5/6 页进行区分。0034 “图计算”是以“图论”为基础的对现实世界的一种“图”结构的抽象表达，以及在这种数据结构上的计算模式。通常，在图计算中，基本的数据结构表达就是：G(V，E)其中，V意为vertex(顶点或者结点)