Hierarchical visualization of a semantic network

• US 20050192926A1
• Filed: 02/17/2005
• Published: 09/01/2005
• Est. Priority Date: 02/18/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Shi Xia, Zhang, Li, Pan, Yue, Su, Zhong
• Application Number:
  US11/060,471
• Publication Number:
  US 20050192926A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

The present invention provides methods, systems and apparatus for generating a visualized hierarchy model for a semantic network, and for browsing a semantic network and a semantic network browser. An example of a semantic network comprises a plurality of concepts and a plurality of relation instances each for connecting two concepts. The method for generating a visualized hierarchy model for a semantic network comprises: determining the similarities among said concepts based on the connection relations of said plurality of concepts in said semantic network; and clustering the concepts with high similarities one by one, so as to form a visualized hierarchy model of said semantic network.

Claims

1. A method comprising generating a visualized hierarchy model for a semantic network, said semantic network comprises a plurality of concepts and a plurality of relation instances each for connecting two concepts, characterized in that the step of generating comprises:

determining similarities among said concepts based on connection relations of said plurality of concepts in said semantic network; and

clustering the concepts with high similarities one by one, so as to form a visualized hierarchy model of said semantic network.

2. The method according to claim 1, characterized in that the step of determining the similarities among said concepts comprises:

calculating a neighbor concept vector for each said concept, said vector represents the connection relation between said concept and other concepts in said semantic network; and

calculating the similarity between two concepts based on the angle between the neighbor concept vectors of said two concepts.

3. The method according to claim 2, characterized in that the step of calculating the similarity between two concepts based on the angle between the neighbor concept vectors of said two concepts comprises:

utilizing the dot product of the neighbor concept vectors of said two concepts to calculate the angle between them, the smaller the angle, the higher the similarity between said two concepts.

4. The method according to claim 1, characterized in that the step of clustering concepts with high similarities one by one so as to form visualized hierarchy model of said semantic network comprises:

merging two concepts with the highest similarity connected by a relation instance; and

repeating above step of merging two concepts, till a predetermined number of concepts are left, so as to form one level of said visualized hierarchy model.

5. The method according to claim 4, characterized in that the step of clustering concepts with high similarities one by one so as to form visualized hierarchy model of said semantic network further comprises:

repeating above steps of merging two concepts and forming one level of said visualized hierarchy model, so as to form a hierarchy model having a plurality of levels.

6. The method according to claim 4, characterized in that said step of merging two concepts comprises:

creating a new concept to replace said two concepts;

merging said two concepts into said new concept; and

updating the relation instance associated with said two concepts using said new concept.

7. The method according to claim 2, characterized in that the step of calculating a neighbor concept vector for each concept comprises:

taking each concept in said semantic network as a dimension, if there is a relation instance between said concept and the concept being calculated the vector, the component is set to 1, otherwise, the component is set to 0.

8. The method according to claim 2, characterized in that each said relation instance is assigned with a connection weight and said step of calculating a neighbor concept vector for each concept comprises:

taking each concept in said semantic network as a dimension, if there is a relation instance between said concept and the concept being calculated the vector, then the component is calculated based on the weight of said relation instance, and if there is no relation instance, the component is set to 0.

9. The method according to claim 2, characterized in that a primary relation type is specified by a user and said step of calculating a neighbor concept vector for each concept comprises:

calculating the similarity between each relation type in said semantic network and said primary relation type specified by the user;

taking each concept in said semantic network as a dimension, if there is a relation instance between said concept and the concept being calculated the vector, then the component is calculated based on the weight of that relation instance and said similarity of relation types, and if there is no relation instance, the component is set to 0.

10. The method according to claim 8, characterized in that the step of calculating the similarity between each relation type in said semantic network and said primary relation type specified by the user comprises:

calculating a relation type feature vector of said relation type in said semantic network, each component in said relation type feature vector corresponds to each concept in said semantic network and is calculated based on the relation instances of said relation type associated with said concept; and

calculating the similarity between said relation type and said user-specified primary relation type based on the angle between the relation type feature vector of said relation type and the relation type feature vector of said user-specified primary relation type.

11. A method comprising browsing a semantic network, said semantic network comprising a plurality of concept and a plurality of relation instances each for connecting two concepts, characterized in that said step of browsing comprises:

using the method according to claim 1 to generate the visualized hierarchy model of said semantic network; and

displaying the content of a corresponding level of the visualized hierarchy model of said semantic network in response to user'"'"'s selection.

12. The method for browsing a semantic network according to claim 11, characterized in that said step of displaying the content of a corresponding level of the visualized hierarchy model of said semantic network comprises:

determining a central concept for display;

when the user selects zoom in, displaying the content of a more detailed level of the visualized hierarchy model of said semantic network, and taking the above determined central concept as the center; and

when the user selects zoom out, displaying the content of a more simplified level of the visualized hierarchy model of said semantic network, and taking the above determined central concept as the center.

13. The method for browsing a semantic network according to claim 12, characterized in that said step of displaying the content of a corresponding level of the visualized hierarchy model of said semantic network further comprises:

if said central concept does not exist in the level to be displayed, taking a concept related to the central concept as the center for display.

22. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visualized hierarchy model for a semantic network, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

23. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating a visualized hierarchy model for a semantic network, said method steps comprising the steps of claim 1.

24. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visualized hierarchy model for a semantic network, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 11.

25. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for browsing a semantic network, said method steps comprising the steps of claim 11.

14. An apparatus for generating a visualized hierarchy model for a semantic network, said semantic network comprising a plurality of concept and a plurality of relation instances each for connecting two concepts, characterized in that said apparatus comprises:

a concept similarity calculation unit for determining the similarities among said concepts based on the connection relations among said plurality of concepts in said semantic network;

a concept clustering unit for clustering concepts with high similarities; and

a hierarchy forming unit for forming visualized hierarchy model of said semantic network level by level utilizing the concept clustering unit.

15. The apparatus according to claim 14, characterized in that the apparatus further comprises:

a neighbor concept vector calculation unit for calculating neighbor concept vector of a concept, said neighbor concept vector represents the connection relation between said concept and each concept in said semantic network;

wherein said concept similarity calculation unit uses said neighbor concept vector to calculate the similarities among concepts.

16. The apparatus according to claim 15, characterized in that said concept similarity calculation unit utilizes the dot product of the neighbor concept vectors of said two concepts to calculate the angle between them, the smaller the angle, the higher the similarity between said two concepts.

17. The apparatus according to claim 14, characterized in that the apparatus further comprises:

a hierarchy calculation unit for calculating the number of levels in the hierarchy model to be generated and the number of concepts in each level based on the amount of content in the original semantic network and the maximum capacity of the screen.

18. The apparatus according to claim 14, characterized in that the apparatus further comprises:

a relation type similarity calculation unit for calculating the similarity between a user-specified primary relation type and each relation type in said semantic network.

19. The apparatus according to claim 18, characterized in that the apparatus further comprises:

a relation type feature vector calculation unit for calculating the relation type feature vector for each relation type in said semantic network, wherein each component in said relation type feature vector corresponds to a concept in said semantic network and is calculated based on the connection instance of that relation type associated with said concept.

wherein said relation type similarity calculation unit calculates the similarity between a relation type and said user-specified primary relation type based on the angle between the relation type feature vector of said relation type and the relation type feature vector of said user-specified primary relation type.

20. A semantic network browser, said semantic network comprising a plurality of concepts and a plurality of relation instances each for connecting two concepts, characterized in that said browser comprises:

the apparatus for generating a visualized hierarchy model for a semantic network according to claim 14;

a graph conversion unit for converting the visualized hierarchy model generated by said apparatus for generating a hierarchy model of a semantic network into a graph mode to display; and

a level switching unit for switching between the levels of said hierarchy model and controlling said graph conversion unit to display, in response to user'"'"'s selection.

21. The semantic network browser according to claim 20, characterized in that said browser further comprises:

a center determination unit for determining a central concept node to be displayed after switching the level of said hierarchy model.

26. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visualized hierarchy model for a semantic network, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 14.