Graph framework using heterogeneous social networks

Patent metadata

Field	Value
Publication number	US-10264048-B2
Application number	US-201615051579-A
Country	US
Kind code	B2
Filing date	Feb 23, 2016
Priority date	Feb 23, 2016
Publication date	Apr 16, 2019
Grant date	Apr 16, 2019

Abstract

In an example embodiment, a supervised machine learning algorithm is used to train a communication reply score model based on an extracted first set of features and second set of features from social networking service member profiles and activity and usage information. When a plurality of member search results is to be displayed, for the member identified in each of the plurality of member search results, the member profile corresponding to the member is parsed to extract a third set of one or more features from the member profile, activity and usage information pertaining to actions taken by the members on the social networking service is parsed to extract a fourth set of one or more features, and the extracted third set of features and fourth set of features is inputted into the communication reply score model to generate a communication reply score, which is displayed visually to a searcher.

First claim

What is claimed is:

1. A computer-implemented method for using a heterogeneous network of nodes to solve a prediction problem, the method comprising:
obtaining social network information;
constructing, based at least partially on the social network information, a graph representing a heterogeneous network of nodes, the graph including a plurality of different types of nodes and a plurality of different types of edges between nodes, each different type of node representing a different type of social network information, at least two of the different types of nodes including a first node type corresponding to a first entity identifying an individual or owner associated with a profile and a second node type corresponding to a second entity not identifying an individual or owner associated with a profile;
defining a plurality of different meta-path types, each meta-path type including a different type of edge between nodes;
determining, based on the prediction problem, one or more pairs of nodes to compare;
for each of the one or more pairs of nodes to compare:
assigning a strength to each of the plurality of different meta-path types for the corresponding pair, the strength based on a count of distinct paths of the corresponding meta-path type, in the graph, between the nodes in the corresponding pair; and
combining the strengths assigned to each of the plurality of different meta-path types for the corresponding pair into a unified strength for a connection for the corresponding pair;
constructing an entity-only graph whose nodes represent only the nodes in the one or more pairs of nodes to compare and having edges each assigned the unified strength for the connection for the corresponding pair; and
running a label propagation algorithm on the entity-only graph to solve the prediction problem, the label propagation algorithm assigning scores to each node in the entity-only graph, the scores indicating a likelihood that a corresponding entity will have a positive outcome to a question posed by the prediction problem.

2. The method of claim 1 , wherein the one or more pairs of nodes contain only nodes of the same type.

3. The method of claim 1 , wherein the assigning a strength includes normalizing the strength based on a number of edges of a single edge type emanating from each of the nodes in the corresponding pair of nodes.

4. The method of claim 1 , wherein the combining of strengths includes calculating the unified strength based on the formula

W

i
,
j

=

1

1
+

exp
⁡

(

-
a

·

w

i
,
j

T

+
ϵ

)

with w i,j =(w i,j 1 , w i,j 2 . . . w i,j N ), which represent N strengths for N types of meta-path, a=(a 1 , a 2 . . . a N ) which are weighting parameters for each type of meta-path, and wherein ∈ is a preset value.

5. The method of claim 1 , wherein the running of the label propagation algorithm comprises:
initializing scores for each node in the entity-only graph to either 0 or 1,
updating each node, in the entity-only graph, considered for the prediction problem, based on scores assigned to direct neighbor nodes and unified strengths assigned to connections between the corresponding node and each direct neighbor node; and
repeating the updating until scores assigned to each node in the entity-only graph converge from one iteration to the next.

6. The method of claim 5 , further comprising ranking the nodes considered for the prediction problem in the entity-only graph based on the scores.

7. The method of claim 5 , wherein the scores are considered to have converged when no score changes more than a preset threshold amount from one iteration to the next.

8. A system comprising:
a non-transitory computer-readable medium having instructions stored there on, which, when executed by a processor, cause the system to perform the following operations:
obtaining social network information;
constructing, based at least partially on the social network information, a graph representing a heterogeneous network of nodes, the graph including a plurality of different types of nodes and a plurality of different types of edges between nodes, each different type of node representing a different type of social network information, at least two of the different types of nodes including a first node type corresponding to a first entity identifying an individual or owner associated with a profile and a second node type corresponding to a second entity not identifying an individual or owner associated with a profile;
defining a plurality of different meta-path types, each meta-path type including a different type of edge between nodes;
determining, based on a prediction problem, one or more pairs of nodes to compare;
for each of the one or more pairs of nodes to compare:
assigning a strength to each of the plurality of different meta-path types for the corresponding pair, the strength based on a count of distinct paths of the corresponding meta-path type, in the graph, between the nodes in the corresponding pair;
combining the strengths assigned to each of the plurality of different meta-paths types for the corresponding pair into a unified strength for a connection for the corresponding pair;
constructing an entity-only graph whose nodes represent only the nodes in the one or more pairs of nodes to compare and having edges each assigned the unified strength for the connection for the corresponding pair; and
running a label propagation algorithm on the entity-only graph to solve the prediction problem, the label propagation algorithm assigning scores to each node in the entity-only graph, the scores indicating a likelihood that a corresponding entity will have a positive outcome to a question posed by the prediction problem.

9. The system of claim 8 , wherein the one or more pairs of nodes contain only nodes of the same type.

10. The system of claim 8 , wherein the assigning a strength includes normalizing the strength based on a number of edges of a single edge type emanating from each of the nodes in the corresponding pair of nodes.

11. T The system of claim 8 , wherein the combining of strengths includes calculating the unified strength based on the formula

W

i
,
j

=

1

1
+

exp
⁡

(

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Zhu Qiang
• Hu Qingbo

Classifications

• H04L67/22

  Electricity · mapped topic

• H04L67/02 Primary

  based on web technology, e.g. hypertext transfer protocol [HTTP] · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L67/306 Primary

  User profiles · CPC title

• H04L67/42

  Electricity · mapped topic