基于大规模社交网络图中资源匹配算法研究
周丽杰;曲洋;于伟海
【摘 要】如何在一个复杂的大型标记网络中搜索需要的资源信息至关重要.摒弃只返回一个结果的精确匹配方式,将大型复杂网络转换为图模型,搜索请求映射为复杂网络中TOP-K个子图,返回匹配搜索请求的TOP-K结果;搜索请求向大型网络映射的策略采用图节点匹配的方式,图中节点之间以跳数定义邻接节点,在指定跳数以内的邻接节点认为满足匹配请求.以Facebook数据为测试数据集,实验结果表明,基于TOP-K搜索的资源匹配算法能够比较准确的实现资源定位.
【期刊名称】《泰山学院学报》
【年(卷),期】2017(039)003
【总页数】6页(P56-61)
【关键词】复杂网络;搜索映射;子图匹配;TOP-K搜索;邻接节点匹配
【作 者】周丽杰;曲洋;于伟海
【作者单位】烟台职业学院电教中心,山东烟台264670;烟台职业学院公共管理系,山东烟台264670;烟台市普通话培训测试中心,山东烟台264003
【正文语种】中 文
【中图分类】TP391
社交场景中诸多抽象节点(比如人和事件)间关联性都可以通过图的结构进行表征，图在表征错综复杂的网络结构时具有非常明显的优势.WikiPedia、Freeba、Facebook和微博等诸多社交平台都可以通过图来很好的展现其内部复杂的结构特征.
如何根据用户的检索请求在复杂的图结构中定位匹配的资源信息是社交网络图的核心问题.基于同构子图、最大公共子图、图编辑距离等图相似匹配方法比较适用于物理和化学方面的网络图结构[1-2]，在处理实体关系和社交网络图时相对较弱.首先，实体关系和社交网络图缺乏明确的规则定义，并且遍布噪声，因此进行严格的拓扑结构相似性定义几乎不可能；其次，实体关系和社交网络图需要考虑节点之间的跳数(需要经过多少节点进行连接)，
并且这些图都附带诸多属性从而极其庞大和复杂，基于编辑距离和最大公共子图等方式难以保证检索的准确性.所以，需要一种新的适用于社交网络图的资源匹配算法[3].
神舟十三号返回
社交网络图资源匹配的目的是为了给用户推荐适合的资源信息列表而非唯一的匹配结果.本文用社交网络图来表征社会化网络，通过指定跳数来界定节点之间是否存在连接关系.将用户的检索请求转换图的表示方式，将用户检索图在社交网络图中进行TOP-K子图匹配，匹配的策略采用节点匹配，节点间距离在H跳数以内则认为匹配成功，将匹配的TOP-K个子图输出给用户作为检索结果,这种匹配方式同时保证了匹配结果的准确性和多样性；另外，基于子图的匹配方式可以很容易进行分布式检索，能够提升查询效率.实验结果表明，本文的子图匹配算法准确率较优于其它图匹配算法.
第一次英文
图匹配的方式是将用户的查询语句转化为查询图，将查询图映射为社交网络图中子图以匹配[4]，将匹配的结果输出给用户.如图1(a)和图1(b)所示.
假设用户的查询请求为：“Find the athlete who is from 'Romania' and won 'gold ' in '3000m’ and 'bronze' in '1500m' both in '1984' Olympics.”.将用户的查询请求转换为查询图的表示方式如图1(a)所示，该查询图在Freeba中最佳匹配结果如图1(b)所示.
可见，查询图所需要匹配的结果是和查询图中节点关联的共同节点，通常情况下，并非每个查询都能找到与查询图中所有节点都匹配的点，因此需要通过最大子图发现检索匹配的查询结果，这正是本文研究的内容.
资源匹配算法的实质是寻找社交网络图中满足用户查询的TOP-K个结果.将用户的查询请求表示为查询图的方式，查询图通过匹配的方式在社交网络图中寻找满足条件的TOP-K个匹配子图并返回.
2.1 子图定义
对于一个图G=(V,E,L),V表示节点集合[5]，E表示边集合，L表示标记(标签)集合，在图G中，每个节点都会被赋予一个标记(标签).假设图G＇=(V＇,E＇,L＇)为G的子图，则
∃v＇,u＇ V＇，(v＇,u＇ )E＇,s.t.,(f(v＇ )V,f(u＇ )V,L(v＇ )L(f(v＇ )),L＇ (u＇ )L(f(u＇ ))(f(v＇ ),f(u＇ ))V
2.2 节点传播权值定义
图中众多节点之间可能并未存在直接连接关系，但是节点之间可以通过其它节点进行连接，我们定义这种连接方式的节点为H跳数邻居节点.
在图2中，节点A和节点C之间并未直接连接，但是可以通过节点D进行连接，则定义节点C为节点A的1(H=1)跳数邻居节点；同理，E节点为B节点2(H=2)跳数邻居节点.因此定义跳数公式如1所示.
摸女生胸部在公式1中，qx和qy表示两个节点，f(qx,qy)表示两个节点间跳数.节点之间的相关性权值通过节点之间的跳数进行定义，节点间跳数越大，表明节点之间的相关性越小[6].节点与目标节点之间的匹配相关性如公式2所示.
在公式2中，α表示权重系数，V表示当前节点，u表示目标节点，L(u)表示目标节点的标签，d(v,u)=i表示节点v和节点u之间跳数，H表示指定跳数以内的邻居节点，l表示当前节点需要匹配的资源标签，I(lL(u))取值为l在节点u的标签范围之内则置1，否则置0，α的取值与H有关，本文中H=3，α取值为0.1.当前节点和标签匹配相关度如公式3所示.
2.3 查询图映射
资源匹配需要将查询图向社交网络图进行映射，定义代价函数Cost(Q,G＇ )[7]，表示查询图和社交网络图中映射子图的相关性，根据相关性的高低输出符合查询条件的TOP-K个结果.
2.3.1 代价函数定义
复合地板保养
对于查询图Q和映射子图G＇，结合公式1中节点之间匹配相关性定义，在映射子图G＇中，可能节点之间并未直接连接，则需要考虑在节点间邻居节点发现时需找最短路径寻优.
公式4表示查询图中节点v映射为标签u的代价，需要分别取查询图AQ(v,l)和匹配子图AG＇ (u,l)的M值，M值的定义方式如公式5所示.公式5表示，当Cost代价函数的值越大时，查询图和匹配子图的相关性越小.对于查询图Q中所有节点的映射代价求和，如公式6所示.
2.3.2 查询匹配
吃什么能下奶对于查询图Q而言，将查询图Q中每个节点映射到社交网络图G中,在图G中找到对应于Q的匹配节点，记节点集合为Q＇，对于Q＇中每个节点，在图G中进行广度优先遍历，搜索在H跳数以内的邻接节点，对所有匹配的H跳数以内邻接节点进行融合构建节点集合E，则对
于E中每个节点记为e，在Q中存在节点子集(q1,q2,…,qn)，使得f(e,qi)≤H，则节点e与节点子集(q1,q2,…,qn)构成的集合称为查询G的一个查询子图，依据此方式，则可得到查询图Q在社交网络图G中查询结果集合，根据公式6中代价函数截取TOP-K返回.
春节小品表1中所示为查询子图的匹配算法.首先，将查询请求转化为查询图的方式，根据查询图中各个节点映射为社交网络图各个匹配节点，根据匹配节点在指定跳数内检索关联节点，最后对关联节点进行融合输出.
实验以Facebook社交网络平台为依托，通过编写中间代码以采用多线程分发的方式对Face book中部分社交数据进行增量导出[8]，导出的格式为JSON格式串，需要对数据进行格式化处理.主要爬取Facebook中用户-签到数据、用户-餐馆数据、用户-电影数据和用户-音乐数据四类数据，如表2所示.
小学课堂游戏Facebook是以用户关系为主流的社交网络平台，现如今Facebook的注册用户已高达22亿，其中错综复杂的关系类型很适合对本文算法进行验证[9].本文挑选100名志愿者分成10组，每组10人，依次对表3中10种查询类型进行人工判断，将该100名志愿者的判断结果作为基准，同时采用本文算法(SRA)、最小编辑距离算法(LEA)和最小公共子图算法(LGA)对
该10种查询类型进行验证，分别比较算法的准确率和F1值，本文中TOP-K的取值中K=10.什么是质押
对表3中查询类型做简要说明，对于查询类型1，“用户-签到-用户”表示当前用户的签到地点，对于该地点，还有哪些人曾经有过签到行为；对于查询类型6，“用户-用户-电影”表示当前用户的关注人当中曾经看过哪些电影.
在图3中，以100名志愿者的人工判断结果作为基准，SRA、LEA和LGA三种算法的匹配结果与基准结果进行比对，在返回的TOP-K结果中，定义K=10，即返回前10条匹配结果.通过三种算法返回的结果在基准结果中比例定义为准确率.可以看出，本文算法的准确率保持在较高水平，准确率的平均值在0.85左右，LEA算法和LGA算法的准确率则相对较低且较为接近，准确率平均值在0.82左右.如果从检索准确率的稳定性来看，三种算法的趋势变化上都较为平滑，没有出现比较突兀的变化.
在图4中，分别对比了SRA算法、LEA算法和LGA算法三种算法在检索结果上的F1值，F1可以反映检索结果的准确率和召回率的稳定性，对于算法而言是一个比较好的衡量指标.从三种算法的走势图上可以看出，相对于LRA算法和LGA算法，本文算法的F1值保持在较高的水平.
社交网络平台，用户之间关系至关重要，本文以用户之间关联关系作为切入点，并将资源节点之间以跳数来定义相关度，将传统的硬连接方式转换为节点跳数的软连接，一方面可以建立资源之间的模糊联系，另一方面也可以更加全面的完善社交网络图模型，提高模型的全面性和完整性.
本文以社交网络模型作为依托，建立模型中各个社交网络节点之间的相关性，将社交网络资源节点以跳数作为纽带构建相互的关联性，将用户的查询请求转换图查询的方式，通过查询图向社交网络图进行映射，将满足匹配条件的TOP-K个子图作为检索结果进行输出，实验以Facebook的用户关系数据作为测试数据集，实验结果表明，本文算法的检索结果准确率和F1值都有了较为明显地的提高.
【相关文献】
[1]Zhang X, Li Z, Lv X, et al.Integrating multiple types of features for event identification in social images[J].Multimedia Tools and Applications, 2016,75(6):3301-3322.
