Detecting content on a social network using links

• US 8,306,922 B1
• Filed: 10/01/2009
• Issued: 11/06/2012
• Est. Priority Date: 10/01/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Panesar, Kiran S., Kunal, Ranveer, Thakur, Madhukar N.
• Primary Examiner(s): OUELLETTE, JONATHAN P
• Application Number:
  US12/571,924
• Time in Patent Office: 1,132 Days
• Field of Search: None
• US Class Current: 705/319
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one implementation, a computer-implemented method includes receiving at information related to users of a social network site, and determining a social network graph for at least a portion of the social network, the graph including a plurality of nodes connected by links, each node corresponding to a user that has a profile page on the social network. The method can also include identifying first nodes from the plurality of nodes as including content associated with a particular subject of interest, and seeding the identified first nodes with first scores. The method can additionally include determining second scores for second nodes based on propagation of the first scores from the first nodes to the second nodes using the links of the social network graph; and providing the determined second scores for the second nodes.

Claims

1. A computer-implemented method comprising:

receiving at a first server system information related to users of a social network site hosted on a second server system;

determining by the first server system a social network graph for at least a portion of the social network from the received information, the graph comprising a plurality of nodes connected by links, each node corresponding to a user that is registered with the social network and that has a profile page on the social network;

identifying first nodes from the plurality of nodes as including content associated with a particular subject of interest;

seeding the identified first nodes with first scores that indicate profile pages for the identified first nodes are positively identified as including content associated with the particular subject of interest;

determining second scores for second nodes of the plurality of nodes based on propagation of the first scores from the first nodes to the second nodes using the links of the social network graph, where;

each of the determined second scores corresponding to a second node indicates a likelihood that a profile page for the second node contains content associated with the particular subject of interest,

a particular second score for a particular second node is determined based on a combination of scores for neighboring nodes that are connected to the particular second node by one or more of the links, and

a particular profile page that is associated with the particular second node is determined to have at least a threshold likelihood of containing content that is associated with the particular subject of interest when at least a portion of the scores for the neighboring nodes exceed a threshold score; and

providing by the first server system the determined second scores for the second nodes.

2. The method of claim 1, wherein the links connecting nodes of the graph comprise acquaintance relationships between two or more users of the social network site.

3. The method of claim 1, wherein the links connecting nodes of the graph comprise common community memberships for two or more users of the social network site.

4. The method of claim 1, wherein the links connecting nodes of the graph comprise a set of common actions performed on the social network site by two or more users of the social network.

5. The method of claim 1, wherein the links connecting nodes of the graph comprise a common set of acquaintance relationships between two or more users of the social network site.

6. The method of claim 1, further comprising repeatedly determining the second scores for the second nodes based on propagation of the first scores from the first nodes to the second nodes using the links of the social network graph and based on propagation of the second scores from the second nodes to among the second nodes using the links of the social network graph.

7. The method of claim 6, wherein the second scores are determined at least a threshold number of iterations.

8. The method of claim 7, wherein the threshold number of iterations comprises at least four iterations.

9. The method of claim 1, wherein propagation of the first scores from the first nodes to the second nodes using the links of the social network graph comprises, for each of the second nodes, computing an average score for all of the nodes connected to the second node in the social graph by links.

10. The method of claim 1, wherein the first scores are propagated from the first nodes to the second nodes through multiple iterations of determining the second scores for the second nodes;

and

the method further comprises, for each of the second nodes, dampening the second score for the second node based upon an iteration at which a score is first propagated to the second node, wherein a score first propagated to a node at an earlier iteration is dampened less than a score first propagated to a node at a later iteration.

11. The method of claim 1, further comprising, for each of the second nodes, boosting the second score for the second node based upon a number of links connecting to the second node, wherein a score for a node having a greater number of links is boosted by a greater amount than a score for a node having a lesser number of links.

12. The method of claim 1, wherein the particular subject of interest comprises at least one of the group consisting adult content and illegal content.

13. The method of claim 1, further comprising identifying a portion of the second nodes that have a second score of at least a threshold level as positively including content associated with the particular subject of interest.

14. The method of claim 1, further comprising:

receiving updated information related to the users of the social network site; and

revising the social network graph using the updated information; and

updating scores for the plurality of nodes based upon the revised social network graph.

15. A system for detecting profile pages on a social network as including content associated with a particular subject of interest, the system comprising:

one or more servers;

an interface for the one or more servers that is configured to receive information related to users of a social network site hosted on a second server system;

a social graph linking module configured to determine a social network graph for at least a portion of the social network from the information received by the interface, the graph comprising a plurality of nodes connected by links, each node corresponding to a user that is registered with the social network and that has a profile page on the social network;

a score seeding component that identifies first nodes from the plurality of nodes as including content associated with a particular subject of interest and that seeds the identified first nodes with first scores that indicate profile pages for the identified first nodes are positively identified as including content associated with the particular subject of interest;

an iterative score propagation module that is configured to determine second scores for second nodes of the plurality of nodes based on propagation of the first scores from the first nodes to the second nodes using the links of the social network graph, where;

each of the determined second scores corresponding to a second node indicates a likelihood that a profile page for the second node contains content associated with the particular subject of interest,

a particular second score for a particular second node is determined based on a combination of scores for neighboring nodes that are connected to the particular second node by one or more of the links, and

a particular profile page that is associated with the particular second node is determined to have at least a threshold likelihood of containing content that is associated with the particular subject of interest when at least a portion of the scores for the neighboring nodes exceed a threshold score; and

a profile content detection module configured to provide the determined second scores for the second nodes.

16. The system of claim 15, wherein the first scores are propagated from the first nodes to the second nodes through multiple iterations of determining the second scores for the second nodes;

and

the system further comprising further comprising a score dampening component that is configured to, for each of the second nodes, dampen the second score for the second node based upon an iteration at which a score is first propagated to the second node, wherein a score first propagated to a node at an earlier iteration is dampened less than a score first propagated to a node at a later iteration.

17. The system of claim 15, further comprising a score boosting component that is configured to, for each of the second nodes, boost the second score for the second node based upon a number of links connecting to the second node, wherein a score for a node having a greater number of links is boosted by a greater amount than a score for a node having a lesser number of links.

18. The system of claim 15, wherein the profile content detection module is further configured to identify a portion of the second nodes that have a second score of at least a threshold level as positively including content associated with the particular subject of interest.

19. A system for detecting profile pages on a social network as including content associated with a particular subject of interest, the system comprising:

one or more servers;

an interface for the one or more servers that is configured to receive information related to users of a social network site hosted on a second server system;

a social graph linking module configured to determine a social network graph for at least a portion of the social network from the information received by the interface, the graph comprising a plurality of nodes connected by links, each node corresponding to a user that is registered with the social network and that has a profile page on the social network;

a score seeding component that identifies first nodes from the plurality of nodes as including content associated with a particular subject of interest and that seeds the identified first nodes with first scores that indicate profile pages for the identified first nodes are positively identified as including content associated with the particular subject of interest;

means for detecting profile pages on a social network as including content associated with a particular subject of interest that is configured to determine second scores for second nodes of the plurality of nodes based on propagation of the first scores from the first nodes to the second nodes using the links of the social network graph, where;

each of the determined second scores corresponding to a second node indicates a likelihood that a profile page for the second node contains content associated with the particular subject of interest,

a particular second score for a particular second node is determined based on a combination of scores for neighboring nodes that are connected to the particular second node by one or more of the links, and

a particular profile page that is associated with the particular second node is determined to have at least a threshold likelihood of containing content that is associated with the particular subject of interest when at least a portion of the scores for the neighboring nodes exceed a threshold score; and

a profile content detection module configured to provide the determined second scores for the second nodes.

20. The system of claim 19, wherein the first scores are propagated from the first nodes to the second nodes through multiple iterations of determining the second scores for the second nodes;

and

the system further comprising further comprising a score dampening component that is configured to, for each of the second nodes, dampen the second score for the second node based upon an iteration at which a score is first propagated to the second node, wherein a score first propagated to a node at an earlier iteration is dampened less than a score first propagated to a node at a later iteration.