• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 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
    • / 14
    • 下载费用:30 金币  

    重庆时时彩实体店代理: 一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201610907676.8

    申请日:

    2016.10.19

    公开号:

    CN106570082A

    公开日:

    2017.04.19

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):G06F 17/30申请日:20161019|||公开
    IPC分类号: G06F17/30; G06Q50/00(2012.01)I 主分类号: G06F17/30
    申请人: 浙江工业大学
    发明人: 宣琦; 赵明浩; 周鸣鸣; 虞烨炜; 傅晨波; 俞立
    地址: 310014 浙江省杭州市下城区潮王路18号浙江工业大学
    优先权:
    专利代理机构: 杭州斯可睿专利事务所有限公司 33241 代理人: 王利强
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201610907676.8

    授权公告号:

    |||

    法律状态公告日:

    2017.05.17|||2017.04.19

    法律状态类型:

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

    摘要

    一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法,包括以下步骤:1)建立朋友关系网络图,随机选取其中90%的朋友关系连边数据为训练集,剩余的10%作为测试集;2)构建两种基于拓扑相似度的朋友关系网络的有权无向图;3)构建两种基于用户行为特征相似度的朋友关系网络的有权无向图;4)使用基于加权??槎鹊纳缤偶觳馑惴?CNM算法)分别对上述四种有权无向图进行社团划分,如果任意两个用户在上述四种社团划分过程中至少有三次或以上被划为同一个社区,则认为这两个用户是朋友关系。本发明将拓扑特征以及行为特征引入到用户朋友关系网络中,通过社团划分,挖掘出两个用户是否是朋友关系。

    权利要求书

    1.一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法,其特征在于:所述挖
    掘方法包括以下步骤:
    S1:数据集提供包括朋友网络与就餐地点、口味信息,首先建立朋友关系网络图,随机
    选取其中设定比例的朋友关系连边数据为训练集,剩余部分作为测试集;
    S2:根据训练集建立朋友关系无权无向图G1=(V,E1),图G1的邻接矩阵A=(aij)v×v,i,j
    ∈{1,2,...,v},其中:

    根据邻接矩阵Av×v=(aij)v×v,i,j∈{1,2,...,v}分别求出如下两种网络拓扑特征:资
    源分配指标(RA),Jaccard指标(J),分别得到下列各拓扑特征矩阵:RAv×v=(RAij)v×v,Jv×v=
    (Jij)v×v,i,j∈{1,2,...,v},如下为各特征矩阵元素表达式:


    其中Γ(i)为节点i的邻居节点的集合,k(z)=|Γ(z)|为节点z的度,各特征矩阵RAv×v,
    Jv×v线性归一化分别为上述矩阵中各元素表达式如下:
    <mrow> <msub> <mover> <mrow> <mi>R</mi> <mi>A</mi> </mrow> <mo>&OverBar;</mo> </mover> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mfrac> <mrow> <msub> <mi>RA</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>-</mo> <mi>min</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>RA</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <mi>m</mi> <mi>a</mi> <mi>x</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>RA</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> <mo>-</mo> <mi>m</mi> <mi>i</mi> <mi>n</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>RA</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>)</mo> </mrow> <mo>,</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>...</mo> <mo>,</mo> <mi>v</mi> <mo>}</mo> </mrow>
    <mrow> <msub> <mover> <mi>J</mi> <mo>&OverBar;</mo> </mover> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mfrac> <mrow> <msub> <mi>J</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>-</mo> <mi>m</mi> <mi>i</mi> <mi>n</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <msub> <mi>J</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <mi>m</mi> <mi>a</mi> <mi>x</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <msub> <mi>J</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> <mo>-</mo> <mi>m</mi> <mi>i</mi> <mi>n</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <msub> <mi>J</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>)</mo> </mrow> <mo>,</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>...</mo> <mo>,</mo> <mi>v</mi> <mo>}</mo> </mrow>
    如上将朋友关系的无权无向图转化为有权无向图,该有权无向图的权值分别对应于上
    述归一化结果的其中之一,构建过程如下:保留用户节点,删除所有朋友连边,根据特征矩
    阵重新确定网络的连边,即连边权值等于特征相似度,权值为0时便是两者特征相似度为0,
    等价于两者没有连边,即不是朋友关系;
    S3:通过用户已有的就餐地点与口味行为的记录数据,分别建立两类二分图,即用户-
    餐馆地区,用户-口味标签,过程如下:定义餐馆二分图G=(X,E,R),其中Xi={x1,x2,...,
    xv},i∈{1,2,...,v}表示v个用户,Ri={r1,r2,...,rn},i∈{1,2,...,n}表示n个餐馆,若用
    户xi,i∈{1,2,...,v}去过餐馆rj,j∈{1,2,...,n},则用有权连边表示该用户去了几次该
    餐馆,权值为dij,i∈{1,2,...,v},j∈{1,2,...,n},即去过的次数,同理,构建用户-口味标
    签二分图G(X,E',T),其中Xi={x1,x2,...,xv},i∈{1,2,...,v}表示v个用户,Ti={t1,
    t2,...,tm},i∈{1,2,...,m}表示m个口味标签,若用户xi选择口味tj,j∈{1,2,...,m},则
    用有权连边表示该用户选择了几次该口味,权值为di'j,i∈{1,2,...,v},j∈{1,2,...,m},
    即选择的次数;所述S3包括以下步骤:
    S3-1:分别根据用户-餐馆与用户-口味标签的二分图,计算出任意两个用户的节点相
    似度,用于表征两个用户之间的行为差异,其中dij表示用户xi去餐馆rj的次数,则用户xi去
    餐馆rj的概率为:
    <mrow> <msub> <mi>p</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mfrac> <msub> <mi>d</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mrow> <munder> <mo>&Sigma;</mo> <mi>k</mi> </munder> <msub> <mi>d</mi> <mrow> <mi>k</mi> <mi>j</mi> </mrow> </msub> </mrow> </mfrac> </mrow>
    根据不相关熵的定义,餐馆rj的熵为:
    <mrow> <msub> <mi>E</mi> <mi>j</mi> </msub> <mo>=</mo> <mo>-</mo> <munderover> <mo>&Sigma;</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>p</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mi>l</mi> <mi>o</mi> <mi>g</mi> <mrow> <mo>(</mo> <msub> <mi>p</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow>
    其中,Ej值越大,表示餐馆rj越受用户欢迎;
    用户xi,xj选择餐馆的特征相似度(RSIM)定义为:

    特征矩阵各元素线性归一化结果为:
    <mrow> <msub> <mover> <mrow> <mi>R</mi> <mi>S</mi> <mi>I</mi> <mi>M</mi> </mrow> <mo>&OverBar;</mo> </mover> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mfrac> <mrow> <msub> <mi>RSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>-</mo> <mi>min</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>RSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <mi>m</mi> <mi>a</mi> <mi>x</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>RSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> <mo>-</mo> <mi>m</mi> <mi>i</mi> <mi>n</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>RSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>)</mo> </mrow> <mo>,</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>...</mo> <mo>,</mo> <mi>v</mi> <mo>}</mo> </mrow>
    同理,在用户-口味标签二分图中,d′ij表示用户xi尝过口味tj的次数,则用户去xi尝过
    口味tj的概率为:
    <mrow> <msubsup> <mi>p</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> <mo>&prime;</mo> </msubsup> <mo>=</mo> <mfrac> <msubsup> <mi>d</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> <mo>&prime;</mo> </msubsup> <mrow> <munder> <mo>&Sigma;</mo> <mi>k</mi> </munder> <msubsup> <mi>d</mi> <mrow> <mi>k</mi> <mi>j</mi> </mrow> <mo>&prime;</mo> </msubsup> </mrow> </mfrac> </mrow>
    根据不相关熵的定义,口味tj的熵为:
    <mrow> <msubsup> <mi>E</mi> <mi>j</mi> <mo>&prime;</mo> </msubsup> <mo>=</mo> <mo>-</mo> <munderover> <mo>&Sigma;</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>p</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> <mo>&prime;</mo> </msubsup> <mi>l</mi> <mi>o</mi> <mi>g</mi> <mrow> <mo>(</mo> <msubsup> <mi>p</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> <mo>&prime;</mo> </msubsup> <mo>)</mo> </mrow> </mrow>
    其中,E′ij值越大,表示口味tj越受用户欢迎;
    则用户选择餐馆在口味上的相似度特征(TSIMij)定义为:

    特征矩阵各元素线性归一化结果为:
    <mrow> <msub> <mover> <mrow> <mi>T</mi> <mi>S</mi> <mi>I</mi> <mi>M</mi> </mrow> <mo>&OverBar;</mo> </mover> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mfrac> <mrow> <msub> <mi>TSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>-</mo> <mi>min</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>TSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <mi>m</mi> <mi>a</mi> <mi>x</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>TSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> <mo>-</mo> <mi>m</mi> <mi>i</mi> <mi>n</mi> <mrow> <mo>(</mo> <msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>TSIM</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mi>v</mi> <mo>&times;</mo> <mi>v</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>)</mo> </mrow> <mo>,</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>...</mo> <mo>,</mo> <mi>v</mi> <mo>}</mo> </mrow>
    S3-2:根据上述两种用户行为特征的重新构建朋友网络,即有权无向图G2=(V,E2),过
    程如下:保留用户节点,删除所有朋友连边,两点之间是否有连边以及连边的权值取决于用
    户行为特征相似度,其中朋友网络的连边E2的权值分别取自于上述两个特征矩阵即

    S4:使用基于加权??槎鹊纳缤偶觳馑惴ǚ直鸲陨鲜隽礁鲇腥ㄎ尴蛲冀猩缤呕?,
    如下为加权无向网络的??槎裙轿?br />
    <mrow> <msub> <mi>Q</mi> <mi>w</mi> </msub> <mo>=</mo> <mfrac> <mn>1</mn> <mrow> <mn>2</mn> <mi>W</mi> </mrow> </mfrac> <munder> <mo>&Sigma;</mo> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </munder> <mrow> <mo>(</mo> <msub> <mi>w</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>-</mo> <mfrac> <mrow> <msub> <mi>s</mi> <mi>i</mi> </msub> <msub> <mi>s</mi> <mi>j</mi> </msub> </mrow> <mrow> <mn>2</mn> <mi>W</mi> </mrow> </mfrac> <mo>)</mo> </mrow> <mi>&delta;</mi> <mrow> <mo>(</mo> <msub> <mi>C</mi> <mi>i</mi> </msub> <mo>,</mo> <msub> <mi>C</mi> <mi>j</mi> </msub> <mo>)</mo> </mrow> <mo>,</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>...</mo> <mo>,</mo> <mi>v</mi> <mo>}</mo> </mrow>
    其中,W是网络中所有边的权值之和,si是节点的强度,即与节点i相连的所有边的权重
    和,wij是网络中节点i与节点j之间的连边的权值,sisj/(2W)是相应的零模型中节点i与节
    点j之间的连边的期望的权值,Ci与Cj分别表示节点i与节点j在网络中所属的社团:如果这
    两个节点属于同一社团,则δ(Ci,Cj)=1;则值为0,所述S4包括以下步骤:
    S4-1:初始化:初始时假设每个节点就是一个独立的社团,即v个社团,选取基于的
    有权无向图为对象,该网络所有边的权值之和为W1,此时??槎戎礠=0,定义对称矩阵Fv×v,
    其中的元素fij表示连接社团和社团中的边权值占所有边权值的比例;定义行的加总
    它表示所有连接了社团中的节点的边权值占总权值的比例,矩阵F和辅助向量
    的元素为fij和ai,初始的fij、ai计算如下:

    ai=si/(2W1)
    其中,fij的非零值是根据所基于的不同特征即拓扑特征、行为特征的有权无向图对象
    决定,初始的??槎仍隽烤卣螃的各元素计算如下:

    得到初始??樵隽烤卣笠院?,就能得到由它每一行的最大元素构成的最大堆H;
    S4-2:从最大堆H中选择max{ΔQij},合并相应的社团Gi和Gj,标记合并后的社团标号为
    j;并更新??槎仍隽烤卣螃、最大堆H和辅助向量
    S4-2-1:ΔQ的更新:删除第i行和第i列的元素,更新第j行和第j列的元素,得到

    S4-2-2:最大堆H的更新:在更新ΔQ后,要更新最大堆中相应的行和列的最大元素;
    S4-2-3:辅助向量的更新如下:
    aj←ai+aj,然后ai=0
    并记录合并以后的??槎戎担?br />Q←Q+max{ΔQij}
    S4-2-4:重复步骤S4-2-2直到网络中所有的节点都归到一个社团内;
    当??槎仍隽烤卣笾凶畲蟮脑赜烧湮?,就停止合并,并认为此时的结果就是基
    于的有权无向图网络的社区结构C1;
    S4-3:选取基于的有权无向网络为对象,重复S4-1过程,就能得到基
    于的有权无向网络的社区结构C2,C3,C4;
    S4-4:根据以上基于四种不同特征包括网络拓扑特征以及用户行为特征的网络社团结
    构,即C1,C2,C3,C4,如果任意两个用户两点在上述四种社团划分过程中至少有三次或以上
    被划为同一个社区,则认为这两个用户是朋友关系。

    说明书

    一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法

    技术领域

    本发明涉及数据挖掘与推荐系统领域,特别是涉及一种基于社交网络拓扑特征以
    及用户行为特征的朋友关系挖掘方法。

    背景技术

    随着互联网尤其是移动互联网的兴起,在海量的信息和数据中挖掘有价值的信息
    呈现给用户,成为电商、社交、新闻、影音等各大主流应用的核心功能。推荐系统特别是个性
    化推荐为每位用户提供精准、及时,甚至是带有惊喜感的个性化信息服务,无论是对于用
    户,还是发布该功能的产品来说,都潜藏着极大的价值。而朋友预测对于用户来说却有不一
    样的惊喜感,因为如果产品推荐出了你现实中的朋友,而这些朋友起初并不存在你的好友
    列表里的话,用户会极大的提高对该产品的好感、忠诚度,这对产品的发展至关重要。本发
    明在于最大可能的挖掘出“潜在”的朋友关系推荐给用户。

    发明内容

    为了克服现有的社交网络中传统的朋友关系网络都可以抽象为无向无权图,只能
    表示两者之间是否为存在朋友关系、无法有效挖掘朋友关系的不足,本发明将网络特征以
    及用户行为特征引入到传统的朋友关系网络中,不仅表示两者是否为朋友,也能表示两个
    朋友关系的强弱程度,从不同的角度考虑两个人的相似度,即社交网络拓扑特征以及用户
    行为特征,使用改进的CNM(Clauset-Newman-Moore)算法进行社团划分,人与人之间存在
    “物以类聚,人以群分”的现象,本发明结合网络拓扑特征和用户行为特征使用改进的CNM算
    法挖掘出两个用户是否存在朋友关系。

    本发明解决其技术问题所采用的技术方案如下:

    一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法,所述挖掘方法包括
    以下步骤:

    S1:数据集提供包括朋友网络与就餐地点、口味信息,首先建立朋友关系网络图,
    随机选取其中设定比例的朋友关系连边数据为训练集,剩余部分作为测试集;

    S2:根据训练集建立朋友关系无权无向图G1=(V,E1),图G1的邻接矩阵A=
    (aij)v×v,i,j∈{1,2,...,v},其中:


    根据邻接矩阵Av×v=(aij)v×v,i,j∈{1,2,...,v}分别求出如下两种网络拓扑特
    征:资源分配指标(RA),Jaccard指标(J),分别得到下列各拓扑特征矩阵:RAv×v=(RAij)v×v,
    Jv×v=(Jij)v×v,i,j∈{1,2,...,v},如下为各特征矩阵元素表达式:



    其中Γ(i)为节点i的邻居节点的集合,k(z)=|Γ(z)|为节点z的度,各特征矩阵
    RAv×v,Jv×v线性归一化分别为上述矩阵中各元素表达式如下:



    如上将朋友关系的无权无向图转化为有权无向图,该有权无向图的权值分别对应
    于上述归一化结果的其中之一,构建过程如下:保留用户节点,删除所有朋友连边,根据特
    征矩阵重新确定网络的连边,即连边权值等于特征相似度,权值为0时便是两者特征相似度
    为0,等价于两者没有连边,即不是朋友关系;

    S3:通过用户已有的就餐地点与口味行为的记录数据,分别建立两类二分图,即用
    户-餐馆地区,用户-口味标签,过程如下:定义餐馆二分图G=(X,E,R),其中Xi={x1,
    x2,...,xv},i∈{1,2,...,v}表示v个用户,Ri={r1,r2,...,rn},i∈{1,2,...,n}表示n个餐
    馆,若用户xi,i∈{1,2,...,v}去过餐馆rj,j∈{1,2,...,n},则用有权连边表示该用户去了
    几次该餐馆,权值为dij,i∈{1,2,...,v},j∈{1,2,...,n},即去过的次数,同理,构建用户-
    口味标签二分图G(X,E',T),其中Xi={x1,x2,...,xv},i∈{1,2,...,v}表示v个用户,Ti=
    {t1,t2,...,tm},i∈{1,2,...,m}表示m个口味标签,若用户xi选择口味tj,j∈{1,2,...,m},
    则用有权连边表示该用户选择了几次该口味,权值为d′ij,i∈{1,2,...,v},j∈{1,2,...,
    m},即选择的次数;所述S3包括以下步骤:

    S3-1:分别根据用户-餐馆与用户-口味标签的二分图,计算出任意两个用户的节
    点相似度,用于表征两个用户之间的行为差异,其中dij表示用户xi去餐馆rj的次数,则用户
    xi去餐馆rj的概率为:


    根据不相关熵的定义,餐馆rj的熵为:


    其中,Ej值越大,表示餐馆rj越受用户欢迎;

    用户xi,xj选择餐馆的特征相似度(RSIM)定义为:


    特征矩阵各元素线性归一化结果为:


    同理,在用户-口味标签二分图中,d′ij表示用户xi尝过口味tj的次数,则用户去xi
    尝过口味tj的概率为:


    根据不相关熵的定义,口味tj的熵为:


    其中,E′ij值越大,表示口味tj越受用户欢迎;

    则用户选择餐馆在口味上的相似度特征(TSIMij)定义为:


    特征矩阵各元素线性归一化结果为:


    S3-2:根据上述两种用户行为特征的重新构建朋友网络,即有权无向图G2=(V,
    E2),过程如下:保留用户节点,删除所有朋友连边,两点之间是否有连边以及连边的权值取
    决于用户行为特征相似度,其中朋友网络的连边E2的权值分别取自于上述两个特征矩阵即

    S4:使用基于加权??槎鹊纳缤偶觳馑惴ǚ直鸲陨鲜隽礁鲇腥ㄎ尴蛲冀猩缤呕?br />分,如下为加权无向网络的??槎裙轿?br />


    其中,W是网络中所有边的权值之和,si是节点的强度,即与节点i相连的所有边的
    权重和,wij是网络中节点i与节点j之间的连边的权值,sisj/(2W)是相应的零模型中节点i
    与节点j之间的连边的期望的权值,Ci与Cj分别表示节点i与节点j在网络中所属的社团:如
    果这两个节点属于同一社团,则δ(Ci,Cj)=1;则值为0,所述S4包括以下步骤:

    S4-1:初始化:初始时假设每个节点就是一个独立的社团,即v个社团,选取基于
    的有权无向图为对象,该网络所有边的权值之和为W1,此时??槎戎礠=0,定义对称矩
    阵Fv×v,其中的元素fij表示连接社团和社团中的边权值占所有边权值的比例;定义行的加
    总它表示所有连接了社团中的节点的边权值占总权值的比例,矩阵F和辅助向量
    的元素为fij和ai,初始的fij、ai计算如下:


    ai=si/(2W1)

    其中,fij的非零值是根据所基于的不同特征即拓扑特征、行为特征的有权无向图
    对象决定,初始的??槎仍隽烤卣螃的各元素计算如下:


    得到初始??樵隽烤卣笠院?,就能得到由它每一行的最大元素构成的最大堆H;

    S4-2:从最大堆H中选择max{ΔQij},合并相应的社团Gi和Gj,标记合并后的社团标
    号为j;并更新??槎仍隽烤卣螃、最大堆H和辅助向量

    S4-2-1:ΔQ的更新:删除第i行和第i列的元素,更新第j行和第j列的元素,得到


    S4-2-2:最大堆H的更新:在更新ΔQ后,要更新最大堆中相应的行和列的最大元
    素;

    S4-2-3:辅助向量的更新如下:

    aj←ai+aj,然后ai=0

    并记录合并以后的??槎戎担?br />

    Q←Q+max{ΔQij}

    S4-2-4:重复步骤S4-2-2直到网络中所有的节点都归到一个社团内;

    当??槎仍隽烤卣笾凶畲蟮脑赜烧湮?,就停止合并,并认为此时的结果就
    是基于的有权无向图网络的社区结构C1;

    S4-3:选取基于的有权无向网络为对象,重复S4-1过程,就能得
    到基于的有权无向网络的社区结构C2,C3,C4;

    S4-4:根据以上基于四种不同特征包括网络拓扑特征以及用户行为特征的网络社
    团结构,即C1,C2,C3,C4,如果任意两个用户两点在上述四种社团划分过程中至少有三次或
    以上被划为同一个社区,则认为这两个用户是朋友关系。

    本发明的有益效果为:本发明挖掘社交网络中的用户关系(即用户关系网络中未
    知的连边状态),最终的预测结果较高,能有效满足实际使用的要求。

    附图说明

    图1为本发明实施例的社交网络中的用户关系发掘方法的流程图。

    具体实施方式

    下面结合附图对本发明做进一步说明。

    参照图1,一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法,所述挖掘
    方法包括以下步骤:

    S1:根据Yelp用户数据集,建立朋友关系网络图,随机选取其中90%的朋友关系连
    边数据为训练集,剩余的10%作为测试集;

    S2:根据两种网络拓扑特征分别构建两种基于拓扑特征的朋友关系网络的有权无
    向图;

    S3:分别构建用户与餐馆、用户与口味的两类二分图,根据上述两类二分图计算出
    两种行为特征相似度矩阵,再构建基于用户行为特征的朋友关系网络的有权无向图;

    S4:使用基于??槎鹊纳缤偶觳馑惴?CNM算法)分别对上述四种有权无向图进行
    社团划分。如果任意两个用户两点在上述四种社团划分过程中至少有三次或以上被划为同
    一个社区,则认为这两个用户是朋友关系。

    所述步骤S1中,Yelp数据集提供包括朋友网络与就餐地点、口味信息,首先建立朋
    友关系网络图,随机选取其中90%的朋友关系连边数据为训练集,剩余的作为测试集。

    所述步骤S2中,根据训练集建立朋友关系无权无向图G1=(V,E1),图G1的邻接矩阵
    A=(aij)v×v,i,j∈{1,2,...,v},其中:


    根据邻接矩阵Av×v=(aij)v×v,i,j∈{1,2,...,v}分别求出如下三种网络拓扑特
    征:资源分配指标(RA),Jaccard指标(J),分别得到下列各拓扑特征矩阵:

    RAv×v=(RAij)v×v,Jv×v=(Jij)v×v,i,j∈{1,2,...,v}。如下为各特征矩阵元素表达
    式:



    其中Γ(i)为节点i的邻居节点的集合,k(z)=|Γ(z)|为节点z的度。各特征矩阵
    RAv×v,Jv×v线性归一化分别为上述矩阵中各元素表达式如下:



    如上可将朋友关系的无权无向图转化为有权无向图,该有权无向图的权值分别对
    应于上述归一化结果的其中之一,构建过程如下:保留用户节点,删除所有朋友连边,根据
    特征矩阵重新确定网络的连边,即连边权值等于特征相似度,权值为0时便是两者特征相似
    度为0,等价于两者没有连边,即不是朋友关系。

    所述步骤S3中,通过Yelp用户已有的就餐地点与口味等行为的记录数据,分别建
    立两类二分图,即用户-餐馆地区,用户-口味标签。过程如下:定义餐馆二分图G=(X,E,R),
    其中Xi={x1,x2,...,xv},i∈{1,2,...,v}表示v个用户,Ri={r1,r2,...,rn},i∈{1,2,...,
    n}表示n个餐馆,若用户xi,i∈{1,2,...,v}去过餐馆rj,j∈{1,2,...,n}。则用有权连边表
    示该用户去了几次该餐馆,权值为dij,i∈{1,2,...,v},j∈{1,2,...,n},即去过的次数。同
    理,可构建用户-口味标签二分图G(X,E',T),其中Xi={x1,x2,...,xv},i∈{1,2,...,v}表
    示v个用户,Ti={t1,t2,...,tm},i∈{1,2,...,m}表示m个口味标签,若用户xi选择口味tj,j
    ∈{1,2,...,m}。则用有权连边表示该用户选择了几次该口味,权值为di'j,i∈{1,2,...,
    v},j∈{1,2,...,m},即选择的次数。

    所述步骤S3包括以下步骤:

    S3-1:分别根据用户-餐馆与用户-口味标签的二分图,计算出任意两个用户的节
    点相似度,用于表征两个用户之间的行为差异。其中dij表示用户xi去餐馆rj的次数,则用户
    xi去餐馆rj的概率为:


    根据不相关熵的定义,餐馆rj的熵为:


    其中,Ej值越大,表示餐馆rj越受用户欢迎。

    用户xi,xj选择餐馆的特征相似度(RSIM)定义为:


    特征矩阵各元素线性归一化结果为:


    同理,在用户-口味标签二分图中,d′ij表示用户xi尝过口味tj的次数,则用户去xi
    尝过口味tj的概率为:


    根据不相关熵的定义,口味tj的熵为:


    其中,E′ij值越大,表示口味tj越受用户欢迎。

    则用户选择餐馆在口味上的相似度特征(TSIMij)定义为:


    特征矩阵各元素线性归一化结果为:


    S3-2:根据上述两种用户行为特征的重新构建朋友网络,即有权无向图G2=(V,
    E2),过程如下:保留用户节点,删除所有朋友连边,两点之间是否有连边以及连边的权值取
    决于用户行为特征相似度,其中朋友网络的连边E2的权值分别取自于上述两个特征矩阵即

    在所述步骤S4中,使用基于加权??槎鹊纳缤偶觳馑惴?CNM算法)分别对上述两
    个有权无向图进行社团划分,如下为加权无向网络的??槎萉w公式为:


    其中,W是网络中所有边的权值之和,si是节点的强度,即与节点i相连的所有边的
    权重和,wij是网络中节点i与节点j之间的连边的权值,sisj/(2W)是相应的零模型中节点i
    与节点j之间的连边的期望的权值,Ci与Cj分别表示节点i与节点j在网络中所属的社团:如
    果这两个节点属于同一社团,则δ(Ci,Cj)=1;则值为0。所述步骤S4包括以下步骤:

    S4-1:初始化:初始时假设每个节点就是一个独立的社团,即v个社团,选取基于
    的有权无向图为对象,该网络所有边的权值之和为W1,此时??槎戎礠=0,定义对称矩
    阵Fv×v,其中的元素fij表示连接社团和社团中的边权值占所有边权值的比例。定义行的加
    总它表示所有连接了社团中的节点的边权值占总权值的比例。矩阵F和辅助向量
    的元素为fij和ai,初始的fij、ai计算如下:


    ai=si/(2W1)

    其中,fij的非零值是根据所基于的不同特征即拓扑特征、行为特征的有权无向图
    对象而决定,初始的??槎仍隽烤卣蟮脑丶扑闳缦拢?br />


    得到初始??樵隽烤卣笠院?,就能得到由它每一行的最大元素构成的最大堆H;

    S4-2:从最大堆H中选择max{ΔQij},合并相应的社团Gi和Gj,标记合并后的社团标
    号为j;并更新??槎仍隽烤卣螃、最大堆H和辅助向量

    S4-2-1:ΔQ的更新:删除第i行和第i列的元素,更新第j行和第j列的元素,得到


    S4-2-2:最大堆H的更新:在更新ΔQ后,要更新最大堆中相应的行和列的最大元
    素;

    S4-2-3:辅助向量的更新如下:

    aj←ai+aj,然后ai=0

    并记录合并以后的??槎戎担?br />

    Q←Q+max{ΔQij};

    S4-2-4:重复步骤S4-2-2直到网络中所有的节点都归到一个社团内;

    在算法运行的整个过程,??槎萉只有一个最大的峰值。当??槎仍隽烤卣笾械淖?br />大元素都小于零以后,Q值就一直下降了。所以,只要当??槎仍隽烤卣笾凶畲蟮脑赜烧?br />变为负,就可以停止合并,并认为此时的结果就是基于的有权无向图网络的社区结构
    C1;

    S4-3:选取基于的有权无向网络为对象,重复S4-1过程,就能得
    到基于的有权无向网络的社区结构C2,C3,C4;

    S4-4:根据以上基于四种不同特征包括网络拓扑特征以及用户行为特征的网络社
    团结构,即C1,C2,C3,C4,如果任意两个用户两点在上述四种社团划分过程中至少有三次或
    以上被划为同一个社区,则认为这两个用户是朋友关系。

    如上所述为本发明在Yelp餐饮平台的用户朋友关系挖掘方法的实施例介绍,本发
    明是结合网络拓扑特征和用户行为特征对传统CNM算法的拓展,最终的预测结果较高,达到
    了实际使用的要求。对发明而言仅仅是说明性的,而非限制性的。本专业技术人员理解,在
    发明权利要求所限定的精神和范围内可对其进行许多改变,修改,甚至等效,但都将落入本
    发明的?;し段?。

    关 键 词:
    一种 结合 网络 拓扑 特征 用户 行为 朋友 关系 挖掘 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:一种结合网络拓扑特征和用户行为特征的朋友关系挖掘方法.pdf
    链接地址://www.4mum.com.cn/p-6092764.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