[發(fā)明專利]一種圖計算方法及引擎

在審

• 申請?zhí)枺?/td>: 201410324671.3
• 申請日: 2014-07-09
• 公開（公告）號: CN104063507A
• 公開（公告）日: 2014-09-24
• 發(fā)明（設計）人: 王緒剛;吳桐;宋磊;張銳
• 申請（專利權）人: 時趣互動（北京）科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京方韜法業(yè)專利代理事務所 11303
• 代理人: 遆俊臣

1.一種圖計算方法，其特征在于，主要包括以下步驟：

A.對圖的原始關系數據進行索引，獲得索引數據，所述圖的頂點和邊上對應所述的索引數據；

B.選擇所述圖的一個或多個頂點為起始節(jié)點，進行廣度優(yōu)先或深度優(yōu)先的多步游走，獲得包括用于候選的多個結束節(jié)點的游走拓撲圖，基于廣度優(yōu)先或深度優(yōu)先的圖游走算法、根據游走路徑中參與的頂點和邊對應的索引數據計算所述起始節(jié)點到達所述結束節(jié)點的到達概率；

C.對計算出的所述到達概率進行排序。

2.根據權利要求1所述的圖計算方法，其特征在于，所述步驟B中對到達概率的計算包括兩次取對數方式的降權操作。

3.根據權利要求1所述的圖計算方法，其特征在于，所述到達概率reach_prob的計算公式為：

reach_prob(startnode,candidate_node)=candidate_value×(1rev_eg_candidate_node_size)eg_popfactor,]]>

其中，eg_popfactor為游走終點圖的配置參數，為浮點值；

rev_eg_candidate_node_size為當前的候選節(jié)點在終點圖的反向圖中的出邊的個數；

candidate_value的計算公式為：

Ⅰ.當為兩步游走時，則所述拓撲圖包括起始圖和終點圖，此時candidate_value＝∑route_value^sg_popfactor×end_value^eg_popfactor×walk_prob；

Ⅱ.當為三步以上游走時，則所述拓撲圖包括起始圖、中間圖和終點圖，設有m個中間圖，m為自然數，此時

candidate_value=walk_prob×Σroute_valuesg_popfactor×route_value1rg1_popfactor×...×route_valuemrgm_popfactor×end_valueeg_popfactor;]]>

其中，walk_prob為本次拓撲圖游走的配置參數，為浮點值；sg_popfactor為起始圖的配置參數，為浮點值；rg_m_popfactor為第m個中間圖的配置參數，為浮點值；

route_value的計算公式為：

route_value=sg_rp_weight×1start_node_size×1sg_scalevalue×log10sg_max_log_valuex,]]>

其中x的值如下：

if(route_node_size>sg_max_log_value||route_node_size<sg_min_log_value){

x＝sg_max_log_value-1；

}else{

x＝route_node_size；

}；

其中，sg_rp_weight為起始圖中對應的邊的權重，start_node_size為起始節(jié)點在起始圖中的對應的邊的出邊的個數；sg_scalevalue為起始圖的浮點型的配置參數，sg_max_log_value和sg_min_log_value為起始圖的浮點型的配置參數，route_node_size為route node在起始圖的反向圖中的出邊的個數；

end_value的計算公式如下：

end_value=eg_rp_weight×1eg_scalevalue×log10eg_max_log_valuex,]]>

其中x的值如下：

if(eg_route_node_size>eg_max_log_value||eg_route_node_size<eg_min_log_value){

x＝eg_max_log_value-1；

}else{

x＝eg_route_node_size；

}；

其中，eg_rp_weight為終點圖中對應的邊的權重，eg_scalevalue為終點圖的浮點型的配置參數，eg_max_log_value和eg_min_log_value為終點圖的浮點型的配置參數，eg_route_node_size為route node在終點圖中對應的邊的出邊個數。