2021, Vol. 47
2. 山东能源新汶矿业集团有限责任公司, 山东 泰安 271200;
3. 东北大学 资源与土木工程学院, 沈阳 110004
2. Shandong Energy Xinwen Mining Group Co., Ltd., Taian, Shandong 271200, China;
3. School of Resources and Civil Engineering, Northeastern University, Shenyang 110004, China
图作为一种抽象的数据结构，能够有效描述现实中各类对象间的复杂关系[1-2]，并广泛应用于社交网[3]、智能交通网[4]与语义Web分析[5]等领域。在图结构中，节点间的相似性度量是各类图查询处理的基础[6]，且可利用得到的查询结果对节点对间的相似程度进行分析。因此，节点相似性查询是图研究领域中的重要问题[7]。
随着大数据[8]与信息技术[9]的应用，图中使用的数据规模逐渐增大，图的节点与边都随着时间推移不断发生动态变化[10-11]。因此，大规模动态图上的节点相似Top-k查询成为图研究领域中的热点与难点问题[12]。现有图节点相似Top-k查询方法多数为迭代计算相似度方法[13]，在迭代过程结束前不能得出结果，造成系统资源浪费，且迭代计算可能造成次优相似度累加结果优于最优解，从而导致查询结果错误[14]。此外，迭代查询方法通常需要遍历全图，未考虑到图结构发生动态变化时如何对查询过程及结果进行更新维护[15]的问题。上述方法在小规模图或静态图[16]上具有较高的查询效率与准确度，但不能满足大规模动态图对相似查询效率及准确度的要求。
本文提出一种基于PageRank的节点相似Top-k查询方法。该方法通过对PageRank进行概率游走约束，避免了概率游走反复选取少数边的情况，并实现将基大图生成多个小规模单向图。同时，结合Monte Carlo模拟法思想，以Top-k取值为约束条件，有效解决次优相似度叠加问题，提高查询效率。依据局部自适应原则提出基大图触发更新策略和单向图集联动更新策略，从而解决查询效率较低的问题。
1 相关工作目前，国内外研究人员针对图节点相似Top-k查询方法的研究众多。文献[17]提出一种基于节点指纹信息进行相似性查询的FR方法，但因为处理节点指纹信息代价较大，所以该方法在大规模图上的查询效率较低。文献[18]提出一种较为精确的迭代计算算法，但该算法在计算相似度的过程中需计算所有节点对的SimRank相似度，存在计算代价过大的问题。文献[19]构建一种新的概率计算框架，该框架通过降维的方式能够有效减少计算量，但在相似度计算中还存在冗余问题，导致查询结果准确度不高。文献[20]通过对SimRank方法进行加权来衡量用户对具体信息的偏好程度，从而实现相似推荐查询，但该方法适用于小规模图查询，在大规模图上存在计算权值及查询对比代价过高的问题。文献[21]提出一种KM方法，它通过预计算节点对相似度的边界来提高查询效率，但是因为该方法需要进行大量预处理操作，且当图更新时需要重新计算相似度边界，所以其在动态图上的查询效率较低。文献[22]提出基于SimRank的概率游走算法，该算法对节点间相似度的计算表示进行改进，查询效率较高，但它无法保证在动态图上的查询准确度。文献[23]提出一种在异构信息网络中的相似性搜索方法，通过x-star模式来实现相似性搜索，但该模式计算代价较高，且在动态图上的查询效率较低。文献[24]提出基于有向图的相似性度量方法，依据图的结构特征综合性衡量相似性，但其处理过程复杂，不能适用于动态图查询。
本文对节点相似Top-k查询方法进行深入研究，并提出一种大规模动态图概率游走约束的节点相似Top-k查询方法。该方法综合考虑大图的数据规模及图动态变化时，对节点相似查询效率及结果集准确度的影响。
2 概率游走约束的相似度累积查询大规模图中游走步数的增大将会直接影响查询效率，为降低基大图节点相似度计算次数，避免Top-k查询中多个“远关系”的叠加结果优于“近关系”的问题，本文引入PageRank概率游走机制，并提出利用单边弱化因子对概率进行约束，将基大图转化为多个小规模单向图，以k取值为约束条件来递增游走步数，实现单向图集上的节点相似Top-k快速累积查询。
2.1 PageRank概率约束定义1 基大图：假设Gr表示基大图，即大规模动态图，节点u为基大图Gr中的节点，（u，v）表示基大图Gr中的边。
定义2 单向图：假设Gs表示基大图中的单向图，则Gs:u∈Gr，v∈No(u)，(u，v)∈Gsi，且v至多取一个节点。其中，节点u为基大图Gr中的节点，在单向图Gs中，（u，v）表示节点u的唯一出边。
当单向图进行选取时，需要从基大图中的查询节点开始，从图中查询节点及其相关节点中随机选出一条路径进行迭代计算，满足每个节点有且仅有一条出边，但可以存在多条入边的情况。为确保随机选取的效率，本文引入PageRank概率游走机制进行路径选取，具体如式（1）所示：
| $ P\left( u \right) = \frac{{1 - d}}{N} + d\sum\limits_{v \in {\rm{in}}\left( u \right)} {\frac{{P\left( v \right)}}{{\left| {{\rm{out}}\left( v \right)} \right|}}} $ | (1) |
其中，P（u）为节点u被访问到的概率，d表示算法继续访问执行的概率，N为基大图中所有的节点数量，in（u）表示所有指向节点u的节点集合，out（v）表示节点v指向其他节点的集合。单向图的大小可根据具体的Top-k查询条件及游走步数i来确定。图 1为基大图转化为单向图的示意图。
|
Download:
|
| 图 1 单向图转化示意图 Fig. 1 Schematic diagram of unidirectional graph conversion | |
从图 1可知，通过概率游走得到的单向图可有效降低图规模。由于单向图是在基大图中通过概率游走机制选取的，若某个或某些节点的出边数较少或只有一条出边，则会导致对PageRank概率游走进行选取时，每个单向图中出现出边的概率较大，进而在相似度计算时会反复叠加这些边，直接影响查询结果的准确度。
为避免上述问题，本文对单向图的各条边引入单边弱化因子参量w=1/Σn，并进行PageRank的概率约束。其中，n为选取次数。将因子参量赋予给单向图中的每条边，若某条边被选中的次数越多，则其对相似度计算的影响力下降越多，重复选中该边的概率将会形成弱化趋势。图 2为单向图集构建示意图。
|
Download:
|
| 图 2 单向图集构建示意图 Fig. 2 Schematic diagram of unidirectional graphs construction | |
如图 2所示，单向图 1与单向图 2均是由图 1中基大图通过弱化重复路径约束生成的单向图。以节点h为例，因为h只有一条出边，所以生成的所有单向图均含有边（h，c）。在单向图 1中，边（h，c）的影响力为1，而在单向图 2中，在单边弱化因子的作用下，其影响力降至为1/2，这说明通过减少某一条边的反复叠加，可有效降低对相似计算结果的影响。
2.2 节点相似Top-k累积查询如果要找到查询节点u的相似节点v，则需要找到节点u和节点v在j步概率游走内的可能相遇节点。由于查询游走步数较多，在基大图上的遍历查询效率很低，因此本文基于Monte Carlo模拟法思想，在整个单向图集中选取若干个查询节点u的j步随机相遇节点，使用节点的累积相似度代替节点真实相似度。
假设弱单向图集为Gs={Gs1，Gs2，…，Gsn}中的单向图，且是相互独立的随机样本，给基大图G中的边随机分配权重值，则由大数定理可得：
| $ \mathop {\lim }\limits_{n \to \infty } P\left\{ {\left| {\frac{1}{n}\sum\limits_{k = 1}^n {{G_{sk}}} - \frac{1}{n}\sum\limits_{k = 1}^n {E\left( {{G_{sk}}} \right)} } \right| < \varepsilon } \right\} = 1 $ | (2) |
由式（2）可知，当n→∞时，基大图中个体和总体的均值差值正向趋近于0。因为弱单向图集中的各个单向图具有极小的相关性，且只与查询节点u的j步游走邻居节点相关，所以由Monte Carlo模拟法可得，当弱单向图集Gs中的各个单向图样本满足路径覆盖时，其计算结果可满足基大图G的误差需求，且具有更快的收敛性。累积相似度计算方法如式（3）所示：
| $ {\rm{Si}}{{\rm{m}}_j}\left( {u, v} \right) = \sum\limits_{j = 1}^j {\sum\limits_{\omega \in V} {\{ {p_j}\left( {u, \omega } \right) \cdot {p_j}\left( {v, \omega } \right) \cdot {c^j} \cdot {I_\omega } \cdot \prod w \} } } $ | (3) |
其中，节点u、v表示概率游走的节点，ω表示相遇节点，Pt(u，ω)及Pt(v，ω)为节点u、v在概率游走过程中出度倒数的乘积，j表示游走步数，
针对基大图游走步数递增会降低图查询效率的问题，本文通过多次引入PageRank概率游走机制，并提出单边弱化因子对其进行概率约束，实现基大图转化为多个单向图集合。由于查询游走步数较多导致基大图上的遍历查询效率较低，因此通过多次随机选取查询节点，利用大数定理进行验证，并计算出节点的累计相似度作为节点的真实相似度，以Top-k取值为基准逐步增大游走步数，实现节点相似Top-k的快速累积查询。
节点相似Top-k算法描述如算法1所示。其中，通过PageRank概率游走机制得到N个单向图的图集，且在每个单向图中，根据概率游走路径找到节点ur的t步相遇节点集，再将节点的游走概率以及单边弱化因子叠乘值代入相似度计算公式中进行计算，以k值作为约束条件，从相遇节点集中选出节点ur的相似节点集，并对节点进行相似度排序得出最终结果。
算法1 节点相似Top-k算法
输入 图G、k，节点u
输出 Top-k相似节点
1.for i=0 to N-1 do{//N is the num of graph
2.Gsi//load the one-way graph；
3.sArr =0；
4.for j=0 to N - 1 do{
5.ur= v；
6.ur；//randomly select a vertex in G
7.for t=1 to J do{
8.
9.
10.}
11.for w∈sSet.Topkset（）do{//key is id of vertice and //calculate
12.Sim（Gsi，w，sLw，sArr）；
13.}
14.return Top-k similar result set
采用概率游走约束的节点进行相似Top-k累积计算，且当计算结果满足Top-k结果集需求时，则立即停止迭代并输出结果集，避免多个“远关系”的叠加结果优于“近关系”的问题，并提高查询效率。算法1中对n个单项图均选取查询节点ur进行概率游走，共找到其j步相遇节点，通过相似度计算公式计算其与查询节点ur的相似度，排序得出查询结果。因此，算法1的时间复杂度为O（n·j）≈O（n）。
3 自适应动态更新节点相似Top-k查询方法在大规模图中可以快速反馈满足条件的查询结果，但当图发生动态变化时，为确保查询结果的准确度，需要对图结构及结果集进行更新维护。本文综合更新效率及准确度2个方面的因素，实现基大图及单向图集的自适应动态更新。
3.1 基大图触发更新对基大图更新时，若每次都进行实时更新，则会导致更新代价过大，且许多变化与查询无关，造成资源浪费；若进行累计更新，则可能导致查询结果错误，降低查询准确度。因此，本文以Top-k查询条件作为更新操作触发点进行自适应触发更新，且触发规则为：判断查询节点u以及u的出边集合{（u，v）|u∈Gr，v∈No(u)，(u，v)∈Gs}是否发生变化，若节点u及（u，v）均发生变化，则采取即时更新策略更新查询；若查询节点u或其出边（u，v）没有发生变化，则继续判断在游走路径过程中的相遇节点是否为起点，并查看起点的边集合{（v，r）|r∈Gr，v∈No(u)，(u，r)∈Gsi}是否变化，若发生变化，此时需采用即时更新策略；若上述2种情形均未发生，则采用累计更新策略对图集进行更新。
3.1.1 即时更新策略对基大图进行更新时，当图中的节点及边变化较大时通常会对图的查询结果产生较大影响，此时需采用即时更新策略。即时更新策略主要是针对查询节点u及其i步邻居节点的变化而言，采用即时更新策略的具体情况可表述为当图发生动态变化时，首先查看节点及其出边是否存在变化，若出现变化，则说明其相似节点等均发生变化，若不对其改变会增加查询结果的错误率；若节点及其出边未发生变化时，则需查看其邻居节点集中各个节点的查询节点i步邻居节点集合是否发生变化，若发生变化，则采用即时更新策略。
即时更新策略的优势在于当发现基大图的变化对查询关联影响较大时，通过该方法可有效保证查询结果的准确度。即时更新算法如算法2所示。其中，判断查询节点u以及u的出边集合{（u，v）| u∈Gr，v∈No(u)，(u，v)∈Gs}是否发生变化，若节点u及边（u，v）发生变化，则即刻进行更新操作；若未发生变化，则继续判断u的邻居节点集中各个节点的查询节点i步邻居节点集合是否发生变化。若查询节点i步邻节点集合与原数据集相比没有发生变化，则停止遍历，查询结果集不变，若发生变化，则分别找出该集合中各个节点的出边及i步邻居节点集合，并重新计算相似查询结果。
算法2 即时更新算法
输入 图G，节点u
输出 新图Gn
1.for u do {
2.if（r-mMap≠mMap）do{//r-mMap is the neighbors //vertex
3.update G and get new graph Gn；}
4.else do{
5.for t∈r-mMap do{
6.t is the Neighborhood vertex，and add t into the r-dMap；
7.if（r-dMap≠dMap）do{
8.update G，get new graph Gn；}
9.for t∈ r-dMap do{
10.if（r-idMap≠idMap）do{
11.update G，get new graph Gn；}
12.}
13.}
14.}
15.return new graph Gn
在算法2中，假设共有n个节点u，对每个节点u开始遍历，若节点u或者其出边发生变化，则立即更新图，因此最少时间复杂度为O（n）；若未发生变化，则需查看其i步邻居节点集合是否发生变化，假设其邻居节点集合数量为k，则最大时间复杂度为O（n·k）≈O（n）。由于算法2中无需额外辅助存储空间，因此空间复杂度为S（1）。
3.1.2 累积更新策略即时更新策略在针对查询节点及其邻居节点发生变化时，能够有效减少查询图时的错误率，但当基大图发生的变化与查询关联较小时，采用即时更新策略会降低效率以及浪费空间。针对这种情况，为提高效率和节省存储空间，本文提出一种累积更新策略，其主要步骤为：先为图查询创建一个辅助存储空间Ω，该空间主要用来记录在一段时间内图的节点与边的变化情况，并以一定的周期对图进行定时更新。为避免某个节点或某条边存在多次删除、增添等情况，在辅助存储空间Ω中，需要先对记录变化进行合并操作，从而进一步提高更新效率。在辅助存储空间Ω中为每条记录添加一个数据变化用到的标签，并令标签的初始值为0。由于节点的增删最终可以转化为边的增删，因此表中只需记录边的增删，并以设定的∆t为周期累加辅助表标签值，进而更新图。
累计更新策略的优势在于能够避免某条边的重复删减情况，通过这种标签的设定不仅可以简化更新操作，而且可有效提高更新效率。累计更新算法如算法3所示。其中，为更新图中每条边的增减情况记录均设定一个标签（u，v，i），若删除边（u，v）则将其标记为（u，v，-1）；若增加边（u，v）则将其标记为（u，v，1）；接下来对更新图中的所有边进行遍历，若标签值为0，则说明不需增加删除边；若标签值为1，则说明需要增加边；若标签值为-1，则说明需要删除边。在统计完所有边的标签后，再对图进行更新操作。
算法3 累计更新算法
输入 图G，更新图
输出 新图Gn
1.for update graph do {
2.（ui，vi，c）// update edges in graph G
3.if（u1，v1，a）=（u2，v2，b）do{
4.merge the same edge in update graph}
5.if c=0 do {//c=0 means no need add and delete edge
6.delete（ui，vi，0），get new update graph；}
7.for graph do{
8.（u1，v1，+1），（uk，vk，c）；//edge of graph and new update //graph；
9.if（u1，v1，1）=（uk，vk，c）do{
10.（u1，v1，1）=（uk，vk，c+1）；//merge edges；
11.if c=0 do{
12.delete（u，v，0），get new graph Gn；}}
13.return new graph Gn
在算法3中，假设图中共有n条边（u，v），并对每条边的记录进行统计，共需统计n次，因此其时间复杂度为O（n）。由于统计一次边需额外开辟辅助空间对记录进行存储，因此空间复杂度为S（n）。
3.2 单向图集联动更新如3.1节所述，当基大图发生变化时，为保证查询的准确度，需要对单向图集进行对应的更新操作。为避免重新选取单向图，本文基于局部更新原则分别对单向图集中所有单向图中边和节点的变化进行局部更新处理，更新策略可表述为：
1）增加边：当基大图中增加某条边（a，b）时，判断边（a，b）中头节点a的出边数Num（a），若节点a出边数Num（a）=0，则需要在每个单向图中均增加边（a，b）；若节点a出边数Num（a）≠0，则需要在所有单向图中为该节点重新选取一条出边。
2）删除边：当基大图中删除了某条边（a，b）时，判断边（a，b）中头节点a的出边数Num（a），若节点a出边数Num（a）=1，则在所有单向图中删除这条边；若节点a出边数Num（a） > 1，则为所有包含被删除边的单向图中的节点a重新选取一条出边。
3）增加节点：当基大图中增加节点u时，主要看其是否有边（u，v）的增加，若没有边的增加，则不需处理单向图集，否则按上述边的增加方法来更新图集。
4）删除节点：当基大图中需要删除某节点时，先要查看是否存在以该节点为头节点或者为尾节点的边，若存在以该节点为头节点的边，则需要在每个单向图中删除这样的节点以及以它们为头节点的边；若存在以该节点为尾节点的边时，则需删除并找到它们的头节点；若不存在上述两种情况，则不需处理。其中，若节点不存在出边则不进行处理，并在每个单向图中为其余节点重新选取一条出边。
图 3为基大图中删除节点f、增加边（g，h）时，单向图集中的单向图更新示意图。
|
Download:
|
| 图 3 基大图与单向图更新示意图 Fig. 3 Schematic diagram of base large graph and unidirectional graph updating | |
如图 3所示，通过对各单向图节点和边的局部操作，可以最大程度地降低单向图集的更新代价，进而提高大规模动态图Top-k查询效率。单向图更新算法如算法4所示，其过程为在单向图集中判断边（u，v）以及节点u是否出现上述某一种情况，并针对上述中某一种情况进行相应操作。
算法4 单向图更新算法
输入 图G，单向图Gis
输出 新单向图Gnis
1.for i=0 to R-1 do {
2.Gis（V，E）//load the one-way graph，V is the vertices set //of Gis，E is the edges set of Gis；
3.edge（u，v）∈E
4.if（delete edge（V，E）in G）do{
5.reselect edge（u，w）in Gis；//edge is one of the out- //edges of u；}
6.else if（add edge（V，E）in G）do{
7.reselect edge（u，w）in Gis；
8.//edge is one of the out-edges of u；}
9.else if（delete u in G）do{
10.delete u in Gis，delete edge（u，*）；
11.//edge is all of the out-edges of u；}
12.else if（add u in G）do{
13.add u in Gis，select edge（u，w）in Gis；}
14.get new one-way graph Gis
15.return new one-way graph Gnis
4 实验结果与分析实验从查询效率、结果可靠性及更新效率等方面验证本文所提方法的有效性。实验的硬件配置为Windows10系统主机、16 GB内存、CPU型号为Intel i5-9300H以及64位操作系统、2 TB硬盘。为验证本文方法的有效性，本文选取5组节点与边数量均不等的数据集，具体如表 1所示。
|
下载CSV 表 1 实验数据集 Table 1 Experimental datasets |
图 4为在5组数据集下，FR、KM、SimRank、P-SimRank方法与本文方法的查询效率对比结果。其中，实验以平均查询时间作为查询效率评价准则。从图 4可以看出，相比其他方法，本文方法具有较高的查询效率。这是由于FR与KM采用的是在结果集中过滤掉不合格节点的方法，造成查询效率较低，SimRank与P-SimRank在计算过程中容易造成相似度叠加问题，因此其适用于小规模的图查询问题，在大图上权值的计算及查询效率较低，本文方法仅需筛选出查询节点的相似节点，因此需要处理的数据量很小，查询效率较高。
|
Download:
|
| 图 4 4种方法的查询效率对比 Fig. 4 Comparison of query efficiency of four methods | |
图 5为4种方法查询结果的可靠性对比。从图 5可以看出，本文方法的准确度与FR、KM方法的原图查询准确度近似，但FR、KM方法存在稳定性较差以及准确度差异较大的问题。本文方法具有较高的可靠性，这是由于SimRank、P-SimRank方法中的节点间相似度计算仅考虑了游走过程中节点相遇总时间的数学期望，无法保证较高的查询准确度。因此，本文方法查询结果的准确度相对较高。
|
Download:
|
| 图 5 4种方法的查询结果可靠性对比 Fig. 5 Reliability comparison of query results of four methods | |
实验通过分析边的更新效率来验证更新策略的有效性，每个图随机选择约80%的插入边和20%的删除边进行更新。表 2为在4个数据集上更新1 000条边的原图与单向图的时间。从表 2可知，本文提出的更新策略在各个数据集上均可达到较高的更新效率。
|
下载CSV 表 2 本文更新策略在4个数据集上的更新效率 Table 2 Update efficiency of the proposed strategy on four datasets |
本文利用大规模动态图概率游走约束条件，提出一种节点相似Top-k查询方法。该方法通过引入PageRank概率游走机制，实现将基大图转化为多个单向图集，并依据Monte Carlo模拟法思想实现Top-k节点相似查询。实验结果表明，与FR、KM、SimRank及P-SimRank方法相比，本文方法的查询准确度与查询效率均有大幅提升，且在查询准确度上表现出良好的稳定性。考虑到图中边的权值对节点相似度的影响以及对图查询与更新的重要性，后续将采用SimRank及其优化方法对加权图的相似节点Top-k查询进行改进，进一步提高查询效率与准确度。
| [1] |
YANG Sibei, LI Guanbi, YU Yizhou.Dynamic graph attention for referring expression comprehension[EB/OL].[2020-07-02].https://arxiv.org/abs/1909.08164.
|
| [2] |
BAI Yunsheng, DING Hao, GU Ken, et al.Learning-based efficient graph similarity computation via multi-scale convolutional set matching[C]//Proceedings of the AAAI Conference on Artificial Intelligence.[S.l.]: AAAI, 2020: 3219-3226.
|
| [3] |
AHMED F, LIU A X, JIN R. Publishing social network graph eigenspectrum with privacy guarantees[J]. IEEE Transactions on Network Science and Engineering, 2020, 7(2): 892-906. DOI:10.1109/TNSE.2019.2901716 |
| [4] |
CHEN Weiqi, CHEN Ling, XIE Yu, et al.Multi-range attentive bicomponent graph convolutional network for traffic forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence.[S.l.]: AAAI, 2020: 3529-3536.
|
| [5] |
FUNEL A.Analysis of the Web graph aggregated by host and pay-level domain[EB/OL].[2020-07-02].https://arxiv.org/pdf/1802.05435.pdf.
|
| [6] |
ZHANG Tianming, GAO Yunjun, ZHENG Baihua, et al. Towards distributed node similarity search on graphs[J]. World Wide Web, 2020, 23(6): 3025-3053. DOI:10.1007/s11280-020-00819-6 |
| [7] |
SONG Youmei, LI Jianbo, HE Tianyue, et al. Probabilistic routing algorithm in delay tolerant network based on node similarity[J]. Computer Engineering, 2016, 42(9): 63-70. (in Chinese) 宋有美, 李建波, 和天玥, 等. 基于节点相似性的容迟网络概率路由算法[J]. 计算机工程, 2016, 42(9): 63-70. DOI:10.3969/j.issn.1000-3428.2016.09.012 |
| [8] |
QIU Jing, CHAI Yunhan, TIAN Zhihong, et al. Automatic concept extraction based on semantic graphs from big data in smart city[J]. IEEE Transactions on Computational Social Systems, 2019, 7(1): 225-233. |
| [9] |
TOAPANTA M, MAFLA E, CISNERO B, et al.Analysis to predict cybercrime using information technology in a globalized environment[C]//Proceedings of the 3rd International Conference on Information and Computer Technologies.Washington D.C., USA: IEEE Press, 2020: 417-423.
|
| [10] |
PANOV M, TSEPA S.Constructing graph node embeddings via discrimination of similarity distributions[C]//Proceedings of 2018 IEEE International Conference on Data Mining Workshops.Washington D.C., USA: IEEE Press, 2018: 1050-1053.
|
| [11] |
NIKOLENTZOS G, MELADIANOS P, VAZIRGIANNIS M.Matching node embeddings for graph similarity[EB/OL].[2020-07-02].https://www.researchgate.net/profile/Polykarpos_Meladianos/publication/314096064_Matching_Node_Embeddings_for_Graph_Similarity/links/58b5523292851ca13e52a0f8/Matching-Node-Embeddings-for-Graph-Similarity.pdf.
|
| [12] |
ZHANG Jing, TANG Jie, MA Cong, et al.Panther: fast Top-k similarity search on large networks[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA: ACM Press, 2015: 1445-1454.
|
| [13] |
XUE Zhengyuan.Top-k selection theory and its application in graph data processing[D].Wuhan: Huazhong University of Science and Technology, 2018.(in Chinese) 薛正元.Top-k选择理论及其在图数据处理中的应用研究[D].武汉: 华中科技大学, 2018. |
| [14] |
ZHANG Liangfu, LI Cuiping, CHEN Hong. Research progress of SimRank computation on big graph:a survey[J]. Chinese Journal of Computers, 2019, 42(12): 2665-2682. (in Chinese) 张良富, 李翠平, 陈红. 大规模图上的SimRank计算研究综述[J]. 计算机学报, 2019, 42(12): 2665-2682. |
| [15] |
MEGHANATHAN N. Unit disk graph-based node similarity index for complex network analysis[J]. Complexity, 2019, 32: 1-22. |
| [16] |
LI M, CHOUDHURY F M, BOROVICA-GAJIC R, et al.CrashSim: an efficient algorithm for computing SimRank over static and temporal graphs[C]// Proceedings of the 36th International Conference on Data Engineering.Washington D.C., USA: IEEE Press, 2020: 1141-1152.
|
| [17] |
KLAPAUKH R, PEARCE D J, MARSHALL S.Towards a vertex and edge label aware force directed layout algorithm[C]//Proceedings of the 37th Australasian Computer Science Conference.New York, USA: ACM Press, 2014: 29-37.
|
| [18] |
HAMEDANI M R, KIM S W. JacSim:an accurate and efficient link-based similarity measure in graphs[J]. Information Sciences, 2017, 414: 203-224. DOI:10.1016/j.ins.2017.06.005 |
| [19] |
DU Lingxia, LI Cuiping, CHEN Hong, et al. Probabilistic SimRank computation over uncertain graphs[J]. Information Sciences, 2015, 295: 521-535. DOI:10.1016/j.ins.2014.10.030 |
| [20] |
PRASENJIT D, GOEL K, AGRAWAL R.P-SimRank: extending SimRank to scale-free bipartite networks[C]// Proceedings of the Web Conference 2020.New York, USA: ACM Press, 2020: 3084-3090.
|
| [21] |
SALAKEN S M, KHOSRAVI A, NAHAVANDI S. Modification on enhanced Karnik⁃Mendel algorithm[J]. Expert Systems with Applications, 2016, 65: 283-291. DOI:10.1016/j.eswa.2016.08.055 |
| [22] |
WANG Hanzhi, WEI Zhewei, YUAN Ye, et al.Exact single-source SimRank computation on large graphs[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data.New York, USA: ACM Press, 2020: 653-663.
|
| [23] |
ZHANG Mingxi, HU Hao, HE Zhenying, et al. Top-k similarity search in heterogeneous information networks with x-star network schema[J]. Expert Systems with Applications, 2015, 42(2): 699-712. DOI:10.1016/j.eswa.2014.08.039 |
| [24] |
JIANG Wanchang, WANG Yinghui. Node similarity measure in directed weighted complex network based on node nearest neighbor local network relative weighted entropy[J]. IEEE Access, 2020, 8: 32432-32441. DOI:10.1109/ACCESS.2020.2971968 |