一种基于图计算的网络实体行为评估算法设计

来源：核心期刊咨询网时间：12

摘要：一.引言 图是一种揭示实体之间关系的语义网络，以符号形式对现实世界的事物及其相互关系进行形式化地描述。其基本组成单位实体-关系-实体三元组，以及实体及其相关属性值对，实体间通过关系相互联结构成网状的结构。现阶段图计算在各个领域都有广泛的应用，

　　一.引言

　　图是一种揭示实体之间关系的语义网络，以符号形式对现实世界的事物及其相互关系进行形式化地描述。其基本组成单位“实体-关系-实体”三元组，以及实体及其相关属性值对，实体间通过关系相互联结构成网状的结构。现阶段图计算在各个领域都有广泛的应用，例如：信息检索/搜索，自然语言理解，问答系统，推荐系统，公安刑侦，社交类业务等。通过图的方式可以更好的展示实体之间的关系。

　　互联网上的各类数据以图的方式存储则可以更清晰直观的展现各个实体的行为以及实体间的关系。一种典型的场景是，当用户产生登录运营商服务器，访问互联网网站，下载文件等行为时，以及运营商内部一些资产服务器上的应用自动访问互联网用于软件更新，一些监控服务对其他资产服务器进行安全扫描等等。运营商都会记录下这些行为日志并进行相应的分析审计。通常的行为日志内容表述如下：

　　A用户 - 在某个时间 - 登录了 - a应用

　　B用户 - 在某个时间 - 访问了 - b网站

　　C用户 - 在某个时间 - 下载了 - c文件

　　A设备 - 在某个时间 - 连接了 - a服务

　　B应用 - 在某个时间 - 扫描了 - C设备

　　上述日志條目中，头尾两端的字段为网络实体(用户，设备，应用等)，中间的字段为关系(登录，访问，下载，连接，扫描等)，时间属性则作为实体或关系的属性值。

　　使用图的形式展现网络实体行为关系更为清晰直观，但存在的问题是当网络规模变大，网络中实体数量大幅增加时，例如实体数量达到数以千计万计时，如此庞大的数量以图的形式展现将变的无法适应，审计人员无法从千万个节点以及千万条边中找出需要关注最有价值的数据。所以采用图的形式展现，和传统数据表形式展现相比同样需要一套数据的评估排序筛选的方法，以找出最有价值的数据。

　　从庞大的图数据集中找出更有价值的数据用于呈现有一些方法，比较常见的一种是在图中为每个实体计算若干项评估指标，例如该实体的最后更新时间，该实体出现的次数，该实体关联关系数等。审计人员从若干项指标中人工选择需要关注的按数值大小按升序或降序排列，最终筛选出topN项实体及其关联关系。

　　进一步出现了上述方法的改进方法，在计算出每个实体的若干项评估指标的基础上，给每种指标赋一个经验权重值，再计算所有指标的加权平均值，审计人员直接按最终的加权平均值的数值大小升序或降序排列实体，同样最终列出topN项实体及其关联关系。

　　针对上述例举的现有方法中的第一种，最大的弊端是通过单个指标的排序并不能完整的评价某个实体的真实情况，并且这种单一维度的评价方法本质上和采用图表方式的存储并无本质区别，并不能很好发挥出图的关联关系特性。

　　针对上述例举的现有方法的改进方法，该方法虽然通过多个指标对实体做了多维度的综合评估，但其对每种指标权重的选择完全基于人工经验，而这种基于经验确定的权重值并不能保证其合理性，不合理的权重值会导致某几项指标在计算加权平均后完全失去了效果，影响最终的评估结果。

　　和上述两种现有方法相比较，本文设计的算法避免了通过单个指标对实体评估的单一性，同时在采用多个指标综合评估的基础上，改进了通过人工设置经验权重这种不太合理的方法，充分利用了图的特性，采用一种基于动态指标的评估方法，可以更加全面准确的对实体进行评估，在图中筛选并展现出更合理的网络实体及其关联关系。

　　二.网络实体行为评估算法设计

　　(一)评估算法总体流程设计

　　运营商记录的其网络中各种网络实体的各种操作记录的日志，提取抽象以后通常都可以用以下属性来描述：

　　上表中举例的行为记录表示：

　　用户Tom在2020.08.01 12：23：45下载了名叫Manual的pdf文件。

　　通常情况下，运营商服务器每时每刻都会记录下上述大量的行为日志，本设计算法收到这些日志后，按如下流程处理：

　　步骤①，获取指定时间范围内运营商服务器所产生的各种行为日志，时间范围长短不做限制。

　　步骤②，将日志中的“实体”以及“作用对象实体”作为顶点，“行为”作为边，采用图的方法存储，即按顶点的关键字分组。

　　步骤③，统计图中上述指定时间范围内的每个顶点的各项指标，即每一组中实体的相关指标，这些指标包括并不限于：顶点上报次数，度中心性，紧密中心性，中介中心性等。

　　步骤④，计算每个实体每种指标在上述时间范围内的数据中相应的概率密度(对于离散型随机变量即指其分布律)，即该计算的概率密度数值只基于本次获取的这批数据得出。

　　步骤⑤，计算每个实体所有指标概率密度结果的数学期望，即求每个顶点所有指标的算术平均值。

　　步骤⑥，将每个实体按按数学期望大小排序，选出其topN实体及其关联关系作为最终结果展现给审计人员查看。

　　(二)实体行为图存储方式设计

　　图是由(V， E)来表示的，对于无向图来说，其中 V =(v0， v1， ... ， vn)，E = { (vi，vj) (0 <= i， j <= n且i 不等于j)}，对于有向图，E = { < vi，vj > (0 <= i， j <= n且i 不等于j)}。V是顶点的集合，E是边的集合。图可以有两种典型的表示方法，一个是邻接矩阵，另一个是邻接链表，这两种方法都可以表示有向图和无向图。

　　邻接矩阵是用两个数组来表示一个图：一个一维数组用来存储每个顶点的信息;一个二维数组(即邻接矩阵)用来存储图中的边或弧信息。对于图G =(V， E)来说，邻接矩阵matrix是一个|V|*|V|的方阵，假设1 <= i， j <= |V|，如果matrix[i][j] == 0，则表示顶点i和顶点j之间没有边相连;反之，如果matrix[i][j] != 0，则表示表示顶点i和顶点j之间有边相连，且matrix[i][j]存储的值即为该边的权重。

　　推荐阅读：计算机信息管理专业论文文献

转载请注明来自：http://www.qikan2017.com/lunwen/dzi/17549.html