Title:
SIMILARITY MEASUREMENT METHOD AND EQUIPMENT
Document Type and Number:
WIPO Patent Application WO/2016/138836
Kind Code:
A1
Abstract:
A similarity measurement method comprises: acquiring directional relations among nodes in a network and determining a transfer matrix (101); computing a constraint matrix according to the transfer matrix and an attenuation factor acquired (102); constructing a system of linear equations, wherein the coefficient matrix of the system of linear equations is the constraint matrix, the variable of the system of linear equations is a correction vector (103); solving the system of linear equations by iteration according to a Jacobi method, and determining the correction vector (104); and computing similarities among the nodes according to the transfer matrix, the attenuation factor and a diagonal correction matrix generated from the correction vector (106). In the method, the Jacobi method is utilized to determine the correction vector and thus similarities among the nodes can be further computed. Various elements of the correction vector are computed independently of one another in every iteration of the Jacobi method and in this way parallel computation can be achieved. Thus, the time for computation can be effectually shortened by use of computer cluster and the time complexity and space complexity during computation can be reduced; in addition, the method can apply to large networks.
Inventors:
LI ZHENGUO (CN)
CHENG JIEFENG (CN)
FAN WEI (CN)
CHENG JIEFENG (CN)
FAN WEI (CN)
Application Number:
PCT/CN2016/074728
Publication Date:
September 09, 2016
Filing Date:
February 26, 2016
Export Citation:
Assignee:
HUAWEI TECH CO LTD (CN)
International Classes:
G06F7/00; G06F17/30
Foreign References:
| CN103177414A | 2013-06-26 | |||
| CN101894123A | 2010-11-24 | |||
| US20090262664A1 | 2009-10-22 | |||
| JP2013196201A | 2013-09-30 |
Other References:
MAEHARA, T. ET AL.: "Efficient SimRank Computation via Linearization", vol. 1411, 26 November 2014 (2014-11-26), pages 7729, XP055417598
WU, DANYU: "the Comparison between Jacobi Iteration and Gauss-Seidel Iteration", JOURNAL OF ZHONGKAI UNIVERSITY OF AGRICULTURE AND TECHNOLOGY, vol. 18, no. 3, 31 December 2005 (2005-12-31), pages 48 - 50, XP009500981
WU, DANYU: "the Comparison between Jacobi Iteration and Gauss-Seidel Iteration", JOURNAL OF ZHONGKAI UNIVERSITY OF AGRICULTURE AND TECHNOLOGY, vol. 18, no. 3, 31 December 2005 (2005-12-31), pages 48 - 50, XP009500981
Attorney, Agent or Firm:
LONGSUN LEAD IP LTD. (CN)
北京龙双利达知识产权代理有限公司 (CN)
北京龙双利达知识产权代理有限公司 (CN)
Download PDF: