Automated social networking graph mining and visualization

Patent metadata

Field	Value
Publication number	US-9990429-B2
Application number	US-78052210-A
Country	US
Kind code	B2
Filing date	May 14, 2010
Priority date	May 14, 2010
Publication date	Jun 5, 2018
Grant date	Jun 5, 2018

Abstract

The automated social networking graph mining and visualization technique described herein mines social connections and allows creation of a social networking graph from general (not necessarily social-application specific) Web pages. The technique uses the distances between a person's/entity's name and related people's/entities names on one or more Web pages to determine connections between people/entities and the strengths of the connections. In one embodiment, the technique lays out these connections, and then clusters them, in a 2-D layout of a social networking graph that represents the Web connection strengths among the related people's or entities' names, by using a force-directed model.

First claim

What is claimed is:

1. A computer-implemented process for identifying social connections among entities, comprising:
using a computing device for: receiving a set of two or more general Web pages that identify social connections between entities; parsing the content of each of the Web pages into information blocks;

identifying names of the entities in the parsed information blocks of each Web page;
ranking the social connections among the entities' names in each of the parsed information blocks by multiplying a relationship distance measure and a context measure of relationship for each pair of identified entities' names in the information block, wherein the relationship distance measure is determined by measuring distance between the identified entities' names in surrounding text in the information block, and wherein the a context measure of relationship between the pair of identified entities in the information block is based on a relationship keyword existing between the names of the two entities in the information block;
integrating the ranked social connections from all the information blocks to determine strengths of the connections between the entities associated with the entities' names; and
displaying a social networking graph based on the strengths of the connections between the entities associated with the entities' names using the integrated ranking of the social connections.

2. The computer-implemented process of claim 1 , wherein ranking the social connections among the entities' names further comprises associating connection weights with entities' names.

3. The computer-implemented process of claim 1 wherein the distance between the names is measured by counting the number of words separating the names in an information block on a Web page.

4. The computer-implemented process of claim 1 , wherein the context measure of a relationship between two entities is determined by determining if a relationship keyword exists between two entities' names in an information block.

5. A computer-implemented process for graphing social connections among entities' names extracted from general Web pages by creating a 2-D graph with a set of vertices representing names, and a set of edges representing social connections, comprising: using a computing device to perform:
receiving a ranked list of social connections between a social graph owner and additional entities obtained from information blocks extracted from the general Web pages, wherein the ranked list was obtained by using a context measure of a relationship and a distance measure of relationship, wherein the context measure of relationship is based on a keyword of a keyword set being found between the name of the social graph owner and a name of an entity in an information block, and wherein the distance measure of relationship is determined by measuring the distance between the name of the social graph owner and a name of an entity;
on a display placing the social graph owner in the center of the 2D graph as a center vertex;
for each of the additional entities, placing a vertex representing a name of an entity in the ranked list in a difference orbit around the center vertex where the shorter the orbit's radius is, the stronger a social connection between the vertex in the orbit and the center vertex is;
clustering the vertices into different clusters according to connectivity between the vertices; placing the vertices in the same cluster closer to each other than to vertices in other clusters; placing clusters of vertices so that clusters of vertices do not overlap each other; and
using a force-directed model to improve the uniformity of the 2D layout.

6. The computer-implemented process of claim 5 wherein the force directed model further comprises a repulsive force between each two vertices and wherein each vertex is either radially or tangentially free or both radially and tangentially free so that it can move according to the repulsive force.

7. The computer-implemented process of claim 5 wherein the force directed model further comprises an attractive force among the edges and wherein each edge is either radially or tangentially free or both radially and tangentially free so that the edge can move according to the attractive force.

8. The computer-implemented process of claim 5 wherein the force directed model further comprises a repulsive force between adjacent orbits and wherein each orbit is either radially or tangentially free or both radially and tangentially free so that the orbit can move according to the repulsive force.

9. The computer-implemented process of claim 5 wherein the force directed model further comprises creating an unpenetratable boundary to isolate the clusters that have no connection to each other.

10. The computer-implemented process of claim 9 wherein each unpenetratable boundary is either radially or tangentially free or both radially and tangentially free so that each unpenetratable boundary can move to isolate clusters that have no connection to each other.

11. The computer-implemented process of claim 5 further comprising minimizing energy in the force-directed model in order to optimize the uniformity of the 2D layout.

12. A system for displaying the social connections among entities' names extracted from general Web pages in the form of creating a 2-D graph with a set of vertices representing names, and a set of edges representing social connections, comprising: a computing device;
a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,
receive a ranked list of social connections between a social graph owner and additional entities obtained from the general Web pages, wherein the ranked list was obtained by using both a measured distance in characters between the name of the social graph owner and the name of a given entity in the content of each one of the general Web pages and a context measure of a-relationship based on a relationship keyword discovered between the name of the social graph owner and the name of the given entity in the content;
on a display place the social graph owner in the center of the 2D graph as a center vertex;
for each entity in the ranked list, place a vertex representing a name of an entity in the ranked list in a difference orbit around the center vertex where the shorter the orbit's radius is, the stronger the social connection between the vertex in the orbit and the center vertex is;
cluster the vertices into different clusters according to the connectivity between the vertices;
use a force-directed model to optimize the uniformity of the 2D layout, wherein the force-directed model comprises:
a repulsive force between each two vertices; an attractive force among the edges; a repulsive force between adjacent orbits; and an unpenetratable boundary to isolate clusters that have no connection to each other.

13. The system of claim 12 wherein each vertex, edge, orbit and unpenetratable boundary are either radially or tangentially free or both radially and tangentially free so as to allow movement according to a force.

14. The system of claim 12 , further comprising a graphical user interface for displaying the 2D graph on the display and allowing a user to manipulate the 2D graph.

15. The system of claim 12 , wherein the graphical user interface further displays the vertices of the 2D graph in color and wherein vertices that are close to each other are displayed in similar colors.

16. The system of claim 12 , wherein an entity can be one of a

Assignees

• Nie Zaiqing
• Cao Yong
• Luo Gang
• Zhang Ruochi
• Liu Xiaojiang
• Ma Yunxiao
• Zhang Bo
• Xu Ying Qing
• Wen Ji Rong
• Microsoft Technology Licensing Llc

Inventors

• Nie Zaiqing
• Cao Yong
• Luo Gang
• Zhang Ruochi
• Liu Xiaojiang
• Ma Yunxiao
• Zhang Bo
• Xu Ying-Qing
• Wen Ji-Rong

Classifications

• G06Q10/40 Primary

  Business processes related to social networking or social networking services · CPC title

• G06F17/30867 Primary

  Physics · mapped topic

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9535 Primary

  Search customisation based on user profiles and personalisation · CPC title

• G06Q10/48

  using social graphs · CPC title