Identifying influential persons in a social network

• US 8,359,276 B2
• Filed: 09/20/2006
• Issued: 01/22/2013
• Est. Priority Date: 09/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhuang, Dong, Zhang, Benyu, Zhang, Heng, Tantrum, Jeremy, Mah, Teresa, Zeng, Hua-Jun, Chen, Zheng, Wang, Jian
• Primary Examiner(s): Ouellette, Jonathan
• Assistant Examiner(s): Ofori-Awuah, Maame
• Application Number:
  US11/533,742
• Publication Number:
  US 20080070209A1
• Time in Patent Office: 2,316 Days
• Field of Search: 705/319
• US Class Current: 705/319
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

An influential persons identification system and method for identifying a set of influential persons (or influencers) in a social network (such as an online social network). The influential persons set is generated such that by sending a message to the set the message will be propagated through the network at the greatest speed and coverage. A ranking of users is generated, and a pruning process is performed starting with the top-ranked user and working down the list. For each user on the list, the user is identified as an influencer and then the user and each of his friends are deleted from the social network users list. Next, the same process is performed for the second-ranked user, the third-ranked user, and so forth. The process terminates when the list of users of the social network is exhausted or the desired number of influencers on the influential person set is reached.

Claims

1. A method for identifying a set of influential persons in a social network, comprising:

using a general-purpose computing device to perform the following;

ranking a list of users in the social network based on a number of friends they have on the social network;

selecting as a first-ranked user a user having a largest number of friends;

designating the first-ranked user as an influencer to include in the set of influential persons before deleting any users from the list of users in the social network;

deleting the first-ranked user and friends of the first-ranked user from the list of users in the social network;

determining that a ranked user has been deleted because that ranked user is a friend of the first-ranked user;

designating a next remaining highest ranked user as the next first-ranked user;

designating the next first-ranked user as an influencer to include in the set of influential persons before deleting any users from the list of users in the social network; and

repeating the above process for subsequent-ranked users to generate the set of influential persons.

2. The method of claim 1, wherein the social network is an online social network.

3. The method of claim 1, further comprising determining a set number corresponding to a number of users in the influential persons set.

4. The method of claim 3, further comprising causing the set number to be determined by a system user.

5. The method of claim 1, further comprising determining that two users are friends if they have a direct connection between them.

6. The method of claim 1, further comprising repeating the above process for subsequent-ranked users to generate the set of influential persons until a number of users in the influential persons set is greater than the set number.

7. The method of claim 6, further comprising repeating the above process for subsequent-ranked users to generate the set of influential persons until there are no more users left in the list of user the social network.

8. The method of claim 7, further comprising displaying the influential persons set to a system user through a graphical user interface in the form of a two-dimensional (2-D) node-link graph.

9. The method of claim 8, further comprising:

displaying the first-ranked user as a center node in the graph; and

displaying links between the first-ranked user and his friends as lines in a radial fashion emanating from the center node.

10. The method of claim 9, further comprising using a width of the line to indicate a strength and importance of a relationship between the first-ranked user and his friends, such that a thicker line represents a stronger relationship between the first-ranked user and his friends, while a thinner line represents a weaker relationship, as compared to the thicker line.

11. The method of claim 10, further comprising using line color to indicate a type of relationship between the first-ranked user and his friends.

12. A computer-readable storage medium having stored thereon computer-executable instructions for generating a set of influential persons in a social network, comprising:

ranking a list of users in the social network based on a number of friends that each user has on the social network to generate a ranking list, such that a first user from the ranking list having a greater number of friends has a higher ranking and a second user from the ranking list having a fewer number of friends than the first user has a lower ranking that the first user;

selecting a user from the ranking list having the highest ranking before deleting any users from the list of users in the social network;

deleting the user having the highest ranking from the list of users in the social network;

deleting friends of the user having the highest ranking from the list of users in the social network;

adding the user having the highest ranking to the set of influential persons;

determining that a ranked user has been deleted because that ranked user is a friend of the user haying the highest ranking;

designating a next remaining highest ranked user as the next user having the highest ranking;

designating the next user having the highest-ranking as an influencer to include in the set of influential persons before deleting any users from the list of users in the social network; and

repeating the above process for each subsequently-ranked user in the ranking list to generate the set of influential persons.

13. The computer-readable storage medium of claim 12, further comprising selecting a set number corresponding to a maximum number of persons contained in the set of influential persons.

14. A computer-implemented process for identifying and visualizing a set of influential persons in an online social network, comprising:

using the computer to perform the following;

ranking a list of users in the online social network based on a criteria to generate a ranking list;

designating a first-ranked user as an influencer to include in the set of influential persons before deleting any users from the list of users in the social network, the influencer defined as having a high network value such that the influencer has the capability to spread a marketing message to a greatest number of people in the online social network in the shortest amount of time as compared to others in the online social network;

generating the set of influential persons by deleting each user in the ranking list and the user'"'"'s friends from the list of users in the online social network, beginning with a highest-ranked user on the ranking list and continuing in descending order until the set of influential persons is filled;

determining that a ranked user has been deleted because that ranked user is a friend of the highest-ranked user;

designating a next remaining highest ranked user as the next highest-ranked user;

designating the next highest-ranked user as an influencer to include in the set of influential persons before deleting any users from the list of users in the social network; and

displaying at least some persons in the set of influential persons to a viewer using a two-dimensional node-link graph that displays a desired person in the set of influential persons in a center of the node-link graph with lines connecting the desired person to other users in the social network of the desired person.

15. The computer-implemented process of claim 14, further comprising:

displaying the desired person as a center node in the center of the node-link graph; and

using lines having different thickness to indicate an importance of a relationship between the desired person and the other users in the social network of the desired person, such that a thicker line represent a stronger relationship between the desired person and a user as compared to a thinner line, which represents a weaker relationship between the desired person and the user.

16. The computer-implemented process of claim 15, further comprising using lines having different colors to represent various types of relationships between the desired person and the other users in his social network.

17. The computer-implemented process of claim 16, further comprising using at least one of the following to indicate the various types of relationships:

(a) an orange line to indicate a user-defined friend, meaning that the desired person defined another user in his social network as a friend;

(b) a green line to indicate a page view, meaning that a user in the desired person'"'"'s social network has visited a web page or a blog of the desired person;

(c) a light blue line to indicate a blog comment, meaning that a user in the desired person'"'"'s social network has commented on the blog;

(d) a yellow line to indicate an instant messenger (IM) chat has occurred between the desired person and a user in his social network;

(e) a dark blue line to indicate that a mixture of no less than two types of relationships as indicated by (a) through (d) have occurred between the desired person and a user in his social network.