# US 2012/0259915 A1 · Method and system for maximizing content spread in social network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0259915 A1
- Document ID: US20120259915A1
- Status: Published application
- Kind: A1
- Application number: 13/080,661
- Filed: 2011-04-06
- Published: 2012-10-11
- Earliest claimed: 2011-04-06
- Assignees: Yahoo! Inc.
- Inventors: Rushi Prafull Bhatt; Rajeev Rastogi; Vineet Shashikant Chaoji; Sayan Ranu
- Web page: https://patentgrep.com/patent/US20120259915A1

## CPC

- G06Q 10/42: Determination of affinities or common interests between users
- G06Q 10/48: using social graphs
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A method, a system and a computer program product for maximizing content spread in a social network are provided. Samples of edges are generated from an initial candidate set of edges. Each edge of the samples of edges has a probability value for content flow. Further, a subset of edges is determined from the samples of edges based on gain corresponding to each edge. Also, each node of the subset of edges is having at least one of less than ‘K’ or equal to ‘K’ incoming edges. Further, the probability of each edge, of the subset of edges, may be incremented. Furthermore, a final set of edges may be determined by ensuring ‘K’ incoming edges. The ‘K’ incoming edges may be ensured by removing one or more incoming edges when a number of the incoming edges for a node of the final set is greater than ‘K’ incoming edge.

## Claims

### Claim 1

A method for maximizing content spread in a social network, the social network comprising a set of nodes and a set of edges between one or more nodes of the set of nodes, the method comprising:
executing steps (a) to (d) for performing one or more functionalities to determine a subset of edges relevant for maximizing flow of a content in the social network, the steps (a) to (d) comprising:
(a) generating one or more samples of edges from an initial candidate set of edges, each edge acquiring a probability value for content flow thereto;
(b) computing gain corresponding to each edge of the one or more samples of edges;
(c) determining the subset of edges from the one or more samples of edges, the subset of edges being determined based on the gain, each node corresponding to each edge of the subset of edges having at least one of less than ‘K’ incoming edges and equal to ‘K’ incoming edges; and
(d) incrementing the probability value of each edge of the subset of edges by a predefined value, the probability value of each edge of the subset of edges being incremented to upgrade the determined subset of edges,
wherein the steps (a) to (d) being performed for a predefined number of iterations;
determining a final set of edges ‘X’ from the upgraded subset of edges, the final set of edges ‘X’ being determined by ensuring ‘K’ incoming edges for each node of the upgraded set of edges; and
outputting the final set of edges ‘X’ to maximize spreading of the content in the social network.

### Claim 2 (depends on 1)

The method of claim 1, wherein each node of the set of nodes corresponding to a user of the social network.

### Claim 3 (depends on 1)

The method of claim 1, wherein each edge of the set of edges corresponding to a connection between two users of the social network.

### Claim 4 (depends on 1)

The method of claim 1 further comprising identifying the initial candidate set of edges comprising candidate edges for a node, the initial candidate set being identified based on one or more characteristics corresponding to the node.

### Claim 5 (depends on 1)

The method of claim 1, wherein the probability value for each edge is initialized as ‘0’.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the subset of edges from the one or more samples of edges comprising determining one or more edges having maximum total gain.

### Claim 7 (depends on 1)

The method of claim 1, wherein ‘K’ is a predefined number of incoming edges for the each node in the subset of edges.

### Claim 8 (depends on 1)

The method of claim 1, wherein determining the final set of edges ‘X’ further comprising:
partitioning the final set of edges ‘X’ into one or more sets ‘Xi’ of edges; and
removing one or more incoming edges for the each node from Xi, the one or more incoming edges being removed when a number of the incoming edges for the each node of Xi is greater than ‘K’ incoming edges.

### Claim 9 (depends on 1)

The method of claim 1 further comprising computing a maximum probability edge from the initial candidate set of edges, the computed maximum probability edge being utilized in computing the gain corresponding to each edge of the one or more samples of edges.

### Claim 10 (depends on 1)

The method of claim 1, wherein the probability value for the each edge of the one or more samples of edges is one of ‘0’ and ‘1’.

### Claim 11

A system for maximizing content spread in a social network, the social network comprising a set of nodes and a set of edges between one or more nodes of the set of nodes, the system comprising:
a functioning module configured to perform one or more functionalities to determine a subset of edges relevant for maximizing flow of a content in the social network, the functioning module comprising:
(a) a sampling module for generating one or more samples of edges from an initial candidate set of edges, each edge having a probability value for content flow thereto;
(b) a computing module for computing gain corresponding to each edge of the one or more samples of edges;
(c) a determining module configured to determine the subset of edges from the one or more samples of edges, the subset of edges being determined based on the computed gain, each node corresponding to each edge of the subset of edges having at least one of less than ‘K’ incoming edges and equal to ‘K’ incoming edges; and
(d) an incrementing module configured to increment the probability value of each edge of the subset of edges by a predefined value, the probability value of each edge of the subset of edges being incremented to upgrade the determined subset of edges,
wherein the functioning module performs one or more functionalities for a predefined number of iterations;
a rounding module configured to determine a final set of edges ‘X’ from the upgraded subset of edges, the final set of edges ‘X’ being determined by ensuring ‘K’ incoming edges for each node of the upgraded set of edges; and
an output module configured to output the final set of edges ‘X’ to maximize spreading of the content in the social network.

### Claim 12 (depends on 11)

The system of claim 11, wherein each node of the set of nodes corresponding to a user of the social network.

### Claim 13 (depends on 11)

The system of claim 11, wherein each edge of the set of edges corresponding to a connection between two users of the social network.

### Claim 14 (depends on 11)

The system of claim 11 further comprising an identification module for identifying the initial candidate set of edges comprising candidate edges for a node, the initial candidate set being identified based on one or more characteristics corresponding to the node.

### Claim 15 (depends on 11)

The system of claim 11, wherein the probability value for each edge is initialized as ‘0’.

### Claim 16 (depends on 11)

The system of claim 11, wherein the determining module capable of determining the subset of edges from the one or more samples of edges when total gain for the subset of edges is maximum.

### Claim 17 (depends on 11)

The system of claim 11, wherein ‘K’ is a predefined number of incoming edges for the each node in the subset of edges.

### Claim 18 (depends on 11)

The system of claim 11, wherein the rounding module further configured to:
perform partitioning of the final set of edges ‘X’ into one or more sets ‘Xi’ of edges; and
remove one or more incoming edges for the each node from Xi, the one or more incoming edges being removed when a number of the incoming edges for the each node of Xi is greater than ‘K’ incoming edges.

### Claim 19 (depends on 11)

The system of claim 11, wherein the computing module further configured to compute a maximum probability edge from the initial candidate set of edges, the computed maximum probability edge being utilized in computing the gain corresponding to each edge of the one or more samples of edges.

### Claim 20 (depends on 11)

The system of claim 11, wherein the probability value for the each edge is one of ‘0’ and ‘1’.

### Claim 21

A computer program product for use with a computer, the computer program product comprising a non-transitory computer usable medium having a computer readable program code embodied therein for maximizing content spread in a social network, the computer readable program code when executed performing a method comprising:
executing steps (a) to (d) for performing one or more functionalities to determine a subset of edges relevant for maximizing flow of a content in the social network, the steps (a) to (d) comprising:
(a) generating one or more samples of edges from an initial candidate set of edges, each edge acquiring a probability value for content flow thereto;
(b) computing gain corresponding to each edge of the one or more samples of edges;
(c) determining the subset of edges from the one or more samples of edges, the subset of edges being determined based on the gain, each node corresponding to each edge of the subset of edges having at least one of less than ‘K’ incoming edges and equal to ‘K’ incoming edges; and
(d) incrementing the probability value of each edge of the subset of edges by a predefined value, the probability value of each edge of the subset of edges being incremented to upgrade the determined subset of edges,
wherein the steps (a) to (d) being performed for a predefined number of iterations;
determining a final set of edges ‘X’ from the upgraded subset of edges, the final set of edges ‘X’ being determined by ensuring ‘K’ incoming edges for each node of the upgraded set of edges; and
outputting the final set of edges ‘X’ to maximize spreading of the content in the social network.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein each node of the set of nodes corresponding to a user of the social network.

### Claim 23 (depends on 21)

The computer program product of claim 21, wherein each edge of the set of edges corresponding to a connection between two users of the social network.

### Claim 24 (depends on 21)

The computer program product of claim 21, wherein the computer program code further identifies the initial candidate set of edges comprising candidate edges for a node, the initial candidate set being identified based on one or more characteristics corresponding to the node.

### Claim 25 (depends on 21)

The computer program product of claim 21, wherein the probability value for each edge is initialized as ‘0’.

### Claim 26 (depends on 21)

The computer program product of claim 21, wherein determining the subset of edges from the one or more samples of edges comprising determining one or more edges having maximum total gain.

### Claim 27 (depends on 21)

The computer program product of claim 21, wherein ‘K’ is a predefined number of incoming edges for the each node in the subset of edges.

### Claim 28 (depends on 21)

The computer program product of claim 21, wherein determining the final set of edges ‘X’ comprising:
partitioning the final set of edges ‘X’ into one or more sets Xi of edges; and
removing one or more incoming edges for the each node from Xi, the one or more incoming edges being removed when a number of the incoming edges for the each node of Xi is greater than ‘K’ incoming edges.

### Claim 29 (depends on 21)

The computer program product of claim 21, wherein the computer program code further computes a maximum probability edge from the initial candidate set of edges, the computed maximum probability edge being utilized in computing the gain corresponding to each edge of the one or more samples of edges.

### Claim 30 (depends on 21)

The computer program product of claim 21, wherein the probability value for the each edge of the one or more samples of edges is one of ‘0’ and ‘1’.
