Title:
GRAPH SIMILARITY CALCULATION SYSTEM, METHOD, AND PROGRAM
Document Type and Number:
WIPO Patent Application WO/2011/001806
Kind Code:
A1
Abstract:
The similarity between graphs having an extremely large number of nodes, such as an SNS, a link of WWW, etc., can be obtained within a reasonable time.
A unique value is provided to a label of a node in a graph. Preferably, the value is a fixed-length bit string. In this case, the length of the bit string is selected to be sufficiently larger than the number of digits by which types of labels can be expressed. With respect to one graph, nodes of the graph are sequentially visited by an existing graph search method, such as a depth-first search, a breadth-first search, and the like. At this time, in the system, when one specific node is visited, a calculation is performed for bit string label values of all nodes adjacent to the specific node and the bit string label value of the specific node, to obtain a bit string value. The hash calculation is performed for the calculated bit string value and the original bit string label value of the node to obtain another bit string label value, and this value becomes the label value of the node. After finishing the visit to all nodes in one graph, the label values of all nodes are rewritten. When the same treatment is performed for another graph which becomes a target of the graph similarity comparison, label values of all nodes in this graph are rewritten. Therefore, with respect to one graph, a ratio of label values which are identical to the label values in another graph, per all nodes is calculated to obtain the similarity.
Inventors:
HIDO SHOHEI (JP)
KASHIMA HISASHI (JP)
KASHIMA HISASHI (JP)
Application Number:
PCT/JP2010/059795
Publication Date:
January 06, 2011
Filing Date:
June 09, 2010
Export Citation:
Assignee:
IBM (US)
HIDO SHOHEI (JP)
KASHIMA HISASHI (JP)
HIDO SHOHEI (JP)
KASHIMA HISASHI (JP)
International Classes:
G06F17/30
Foreign References:
| JPH07334366A | 1995-12-22 | |||
| JPH07334366A | 1995-12-22 | |||
| US6473881B1 | 2002-10-29 |
Other References:
SHIGEO ABE: "Introduction of Support Vector Machines for Pattern Classification-VI : Current Topics", SYSTEM/SEIGYO/JOHO, vol. 53, no. 5, 15 May 2009 (2009-05-15), pages 41 - 46, XP008150377
TAKAHISA WADA ET AL.: "Bubun Kozo ni Motozuku Kozo Ruijisei o Mochiita Tokucho Chushutsu System to Sono Oyo", JOURNAL OF THE DBSJ, vol. 7, no. 1, 27 June 2008 (2008-06-27), pages 187 - 192, XP008150379
"Proc. of the Nineth IEEE International Conference on Data Mining (ICDM2009), [online], Edited by W. Wang et al. IEEE, December 6-9, 2009", 5 July 2010, article HIDO, SHOHEI ET AL.: "A Linear-Time Graph Kernel", pages: 179 - 188, XP031585332
SHOHEI HIDO ET AL.: "A Fast Graph Kernel Using Neighborhood Hash", DAI 12 KAI INFORMATION- BASED INDUCTION SCIENCES (IBIS) WORKSHOP (IBIS 2009), 19 October 2009 (2009-10-19), XP008150380, Retrieved from the Internet [retrieved on 20100705]
See also references of EP 2442239A4
TAKAHISA WADA ET AL.: "Bubun Kozo ni Motozuku Kozo Ruijisei o Mochiita Tokucho Chushutsu System to Sono Oyo", JOURNAL OF THE DBSJ, vol. 7, no. 1, 27 June 2008 (2008-06-27), pages 187 - 192, XP008150379
"Proc. of the Nineth IEEE International Conference on Data Mining (ICDM2009), [online], Edited by W. Wang et al. IEEE, December 6-9, 2009", 5 July 2010, article HIDO, SHOHEI ET AL.: "A Linear-Time Graph Kernel", pages: 179 - 188, XP031585332
SHOHEI HIDO ET AL.: "A Fast Graph Kernel Using Neighborhood Hash", DAI 12 KAI INFORMATION- BASED INDUCTION SCIENCES (IBIS) WORKSHOP (IBIS 2009), 19 October 2009 (2009-10-19), XP008150380, Retrieved from the Internet
See also references of EP 2442239A4
Attorney, Agent or Firm:
UENO Takeshi et al. (JP)
Tsuyoshi Ueno (JP)
Tsuyoshi Ueno (JP)
Download PDF:
Previous Patent: RACKET STRING, METHOD FOR MANUFACTURING SAME, AND RACKET STRUNG WITH SAME
Next Patent: CONNECTOR
Next Patent: CONNECTOR