Techniques for inferring an organizational hierarchy from a social graph

• US 9,049,249 B2
• Filed: 01/31/2013
• Issued: 06/02/2015
• Est. Priority Date: 11/26/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Zhang, Ximeng, Wang, Guan, Zhao, Yuchen, Liu, Shaobo, Sutherland-Wong, Christian, Derezin, Mike
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US13/756,142
• Publication Number:
  US 20140214945A1
• Time in Patent Office: 852 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 50/00 Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism healthcare informatics G16H
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 67/306 User profiles

Abstract

A method, system and article of manufacture for determining a global hierarchy of an entity by computing subjective coherence strength between nodes of first members of a social network service, computing objective entanglement strength between nodes of second members of the social network service, using subjective coherence strength and objective entanglement strength, compute the pairwise latent relationship probabilities between different ones of the nodes of the social network service, and using the pairwise relationship probabilities, compute the global hierarchy relationship.

Claims

1. A method of determining global hierarchy of an organization, the method comprising:

computing, by at least one computer processor, subjective coherence strength, which quantifies subjective relationship strength between nodes of first members of a social network service based on information supplied by the first members;

computing objective entanglement strength, which quantifies objective similarity between nodes of second members of the social network service based on the commonality of the second members recognized by a general crowd;

using the subjective coherence strength and the objective entanglement strength to compute pairwise latent relationship probabilities, which measure the latent hierarchy relation probabilities between pairs of different nodes of the social network service; and

using the pairwise latent relationship probabilities to compute a global hierarchy relationship comprising an organization chart for at least two levels of the organization.

2. The method of claim 1, the computing objective entanglement strength comprising determining co-viewed members of the social network service and using information from the nodes of the co-viewed members for computing objective entanglement strength.

3. The method of claim 2, the determining co-viewed members comprising collaboratively filtering information from the nodes of the social network.

4. The method of claim 3 comprising selecting a latent relation candidate set by computing pairwise job title similarity.

5. The method of claim 4 wherein pairwise job title similarity is computed as

6. The method of claim 5 wherein the latent relation candidate set Φ

_u for node u is

Φ

_u={v|e_uvε

E, S(t_u, t_v)>

ρ

}

where ρ

is a threshold to control the title similarity to be higher than a certain level.

7. The method of claim 1, the computing subjective coherence strength comprising computing ego networks from nodes of members of the social network service and performing a graph layout algorithm for the ego networks.

8. The method of claim 1 wherein the ego network of a node u is Ω

_u={N_u,E_Nu}

where Nu is the set of adjacent nodes of u, and

E_Nu={eij|i, jε

Nu} is the edges among u'"'"'s neighbors.

9. The method of claim 2 wherein the objective entanglement is computed as

O(x, y)=cos(σ

(Ux),σ

(Uy)),

where Ux and Uy are the vector of users who have seen x'"'"'s profile and y'"'"'s profile respectively, and

σ

is a normalization function.

10. The method of claim 1 wherein the pairwise latent relationship probabilities are

11. The method of claim 1 wherein using the pairwise latent relationship probabilities to compute the global hierarchy relationship comprises using a reduced Markov Decision Process.

12. The method of claim 11 wherein the reduced Markov Decision Process includes a reward function based on the seniorities of two related members of the social network service.

13. The method of claim 11 wherein the reduced Markov Decision Process maximizes transition probability p and action a in accordance with

14. A machine-readable storage device having embedded therein a set of instructions which, when executed by a machine, causes execution of the following operations:

computing, by at least one computer processor, subjective coherence strength, which quantifies subjective relationship strength between nodes of first members of a social network service based on information supplied by the first members;

computing objective entanglement strength, which quantifies objective similarity between nodes of second members of the social network service based on the commonality of the second members recognized by a general crowd;

using the subjective coherence strength and the objective entanglement strength to compute pairwise latent relationship probabilities, which measure the latent hierarchy relation probabilities between pairs of different nodes of the social network service; and

using the pairwise latent relationship probabilities to compute a global hierarchy relationship comprising an organization chart for at least two levels of the organization.

15. The machine-readable storage device of claim 14, the computing objective entanglement strength comprising determining co-viewed members of the social network service and using information from the nodes of the co-viewed members for computing objective entanglement strength.

16. The machine-readable storage device of claim 15, the determining co-viewed members comprising collaboratively filtering information from the nodes of the social network.

17. The machine-readable storage device of claim 16 comprising selecting a latent relation candidate set by computing pairwise job title similarity.

18. The machine-readable storage device of claim 17 wherein pairwise job title similarity is computed as

19. The machine-readable storage device of claim 18 wherein the latent relation candidate set Φ

_u for node u is

Φ

_u={v|e_uvε

E, S(t_u, t_v)>

ρ

}

where ρ

is a threshold to control the title similarity to be higher than a certain level.

20. The machine-readable storage device of claim 14, the computing subjective coherence strength comprising computing ego networks from nodes of members of the social network service and performing a graph layout algorithm for the ego networks.

21. The machine-readable storage device of claim 14 wherein the ego network of a node u is Ω

_u={N_u,E_Nu}

where Nu is the set of adjacent nodes of u and

E_Nu={eij|i, jε

Nu} is the edges among u'"'"'s neighbors.

22. The machine-readable storage device of claim 15 wherein the objective entanglement is computed as

O(x, y)=cos(σ

(Ux), σ

(Uy)),

where Ux and Uy are the vector of users who have seen x'"'"'s profile and y'"'"'s profile respectively,

and σ

is a normalization function.

23. The machine-readable storage device of claim 14 wherein the pairwise latent relationship probabilities are

24. The machine-readable storage device of claim 14, wherein using the pairwise relationship probabilities to compute the global hierarchy relationship comprises using a reduced Markov Decision Process.

25. The machine-readable storage device of claim 24 wherein the reduced Markov Decision Process includes a reward function based on the seniorities of two related members of the social network service.

26. The machine-readable storage device of claim 24 wherein the reduced Markov Decision Process maximizes transition probability p and action a in accordance with

27. A system comprising:

one or more computer processors configured to

compute subjective coherence strength, which quantifies subjective relationship strength between nodes of first members of a social network service based on information supplied by the first members;

compute objective entanglement, which quantifies objective similarity between nodes of second members of the social network service based on the commonality of the second members recognized by a general crowd;

use the subjective coherence strength and the objective entanglement strength to compute pairwise latent relationship probabilities, which measure the latent hierarchy relation probabilities between pairs of different nodes of the social network service; and

use the pairwise latent relationship probabilities to compute a global hierarchy relationship comprising an organization chart for at least two levels of the organization.

28. The system of claim 27, the at least one computer processor configured to compute objective entanglement strength by determining co-viewed members of the social network service and use information from the nodes of the co-viewed members for computing objective entanglement strength.

29. The system of claim 28, the at least one computer processor configured to determine co-viewed members by collaboratively filtering information from the nodes of the social network.

30. The system of claim 29 the at least one computer processor configured to select a latent relation candidate set by computing pairwise job title similarity.

31. The system of claim 27, the at least one computer processor configured to compute subjective coherence strength by computing ego networks from nodes of members of the social network service and performing a graph layout algorithm for the ego networks.

32. The system of claim 27, the at least one computer processor configured to use the pairwise latent relationship probabilities to compute the global hierarchy relationship by using a reduced Markov Decision Process.

33. The system of claim 32 wherein the reduced Markov Decision Process includes a reward function based on the seniorities of two related members of the social network service.

34. The system of claim 32 wherein the reduced Markov Decision Process maximizes transition probability p and action a in accordance with