# US 2017/0286975 A1 · Data Infrastructure and Method for Estimating Influence Spread in Social Networks

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

- Number: US 2017/0286975 A1
- Document ID: US20170286975A1
- Status: Published application
- Kind: A1
- Application number: 15/447,765
- Filed: 2017-03-02
- Published: 2017-10-05
- Earliest claimed: 2016-04-01
- Assignees: Sysomos L.P.
- Applicants: Sysomos L.P.
- Inventors: Koushik PAL; Zisis Paraskevas POULOS
- Web page: https://patentgrep.com/patent/US20170286975A1

## CPC

- G06Q 30/0201: Market modelling; Market analysis; Collecting market data
- G06N 5/02: Knowledge representation; Symbolic representation
- G06N 5/04: Inference or reasoning models
- G06Q 10/46: Determination of level of influence of users within social networking services
- 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
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A system and method are provided for determining influence spread in social networks. The method includes generating a plurality of samples using a computing device, each sample corresponding to a collection of all edge weights for a social network graph topology; and allocating, by the computing device, the plurality of samples into at least one batch, a size of which is being determined according to a number of threads and global memory space available in a multi-processor platform. For each batch, the method includes parallel processing the samples in that batch using the multi-processor platform to generate results corresponding to a spread of each graph node per sample in that batch; storing results of that batch in the global memory accessible to the multi-processor platform; and sending the results to the computing device. The method also includes computing, using the computing device, an average spread of each node across all samples in all batches; and determining, from the average spreads, one or more nodes having a largest spread.

## Claims

### Claim 1

A method of determining influence spread in social networks, the method comprising:
generating a plurality of samples using a computing device, each sample corresponding to a collection of all edge weights for a social network graph topology;
allocating, by the computing device, the plurality of samples into at least one batch, a size of which is being determined according to a number of threads and global memory space available in a multi-processor platform;
for each batch:
parallel processing the samples in that batch using the multi-processor platform to generate results corresponding to a spread of each graph node per sample in that batch; and
storing results of that batch in the global memory accessible to the multi-processor platform;
computing, using the computing device, an average spread of each node across all samples in all batches; and
determining, from the average spreads, one or more nodes having a largest spread.

### Claim 2 (depends on 1)

The method of claim 1, wherein the one or more nodes having a largest spread correspond to a first seed, and wherein the method is repeated until a predetermined number of seeds is obtained.

### Claim 3 (depends on 1)

The method of claim 1, further comprising outputting the results to a social media intelligence application.

### Claim 4 (depends on 1)

The method of claim 1, wherein the multi-processor platform is a graphics processing unit (GPU).

### Claim 5 (depends on 1)

The method of claim 1, wherein the multi-processor platform is a multi-core processor.

### Claim 6 (depends on 1)

The method of claim 1, wherein each sample is processed in a thread by applying a Naïve Sampling algorithm.

### Claim 7 (depends on 1)

The method of claim 1, wherein each sample is processed in a thread by applying a Cohen's Neighborhood Size Estimation algorithm.

### Claim 8 (depends on 1)

The method of claim 1, wherein edge weight orders are stored in the global memory accessible to the multi-processor platform by storing the weights for each edge from all samples together in respective blocks of the memory.

### Claim 9 (depends on 1)

The method of claim 1, wherein blocks of the memory accessible to the multi-processor platform are fetched at the same time at each memory call using a texture memory structure.

### Claim 10 (depends on 1)

The method of claim 1, wherein an L1 cache for the multi-processor platform is disabled such that an L2 cache is utilized to reduce wasteful data at each memory call.

### Claim 11 (depends on 1)

The method of claim 1, wherein the social network graph topology has a distribution associated with each edge.

### Claim 12 (depends on 11)

The method of claim 11, wherein the distribution is an exponential distribution with a parameter that varies from edge to edge.

### Claim 13 (depends on 1)

The method of claim 1, wherein the parallel processing of each sample considers a deadline time.

### Claim 14

A computing system for determining influence spread in social networks, the system comprising:
a central processor system, a multi-processor platform, and a global memory;
the central processor system configured to generate a plurality of samples, each sample corresponding to a collection of all edge weights for a social network graph topology;
the central processor system configured to allocate the plurality of samples into at least one batch, a size of which is being determined according to a number of threads and global memory space available in the multi-processor platform;
for each batch:
the multi-processor platform configured to parallel process the samples in that batch to generate results corresponding to a spread of each graph node per sample in that batch; and
the global memory configured to store results of that batch, the global memory accessible to the multi-processor platform;
the central processor system configured to compute an average spread of each node across all samples in all batches; and
the central processor system configured to determine, from the average spreads, one or more nodes having a largest spread.

### Claim 15 (depends on 14)

The computing system of claim 14, wherein the multi-processor platform comprises a graphics processing unit (GPU).

### Claim 16 (depends on 14)

The computing system of claim 14, wherein the one or more nodes having a largest spread correspond to a first seed, and wherein the system is configured to repeatedly process the samples until a predetermined number of seeds is obtained.

### Claim 17 (depends on 14)

The computing system of claim 14 wherein the central processor system is configured to output the results to a social media intelligence application.

### Claim 18 (depends on 14)

The computing system of claim 14, wherein the multi-processor platform is a multi-core processor.

### Claim 19 (depends on 14)

The computing system of claim 14, wherein each sample is processed in a thread by applying a Naïve Sampling algorithm.

### Claim 20 (depends on 14)

The computing system of claim 14, wherein each sample is processed in a thread by applying a Cohen's Neighborhood Size Estimation algorithm.

### Claim 21 (depends on 14)

The computing system of claim 14, wherein edge weight orders are stored in the global memory accessible to the multi-processor platform by storing the weights for each edge from all samples together in respective blocks of the global memory.

### Claim 22 (depends on 14)

The computing system of claim 14, wherein blocks of the global memory accessible to the multi-processor platform are fetched at the same time at each memory call using a texture memory structure.

### Claim 23 (depends on 14)

The computing system of claim 14, wherein an L1 cache for the multi-processor platform is disabled such that an L2 cache is utilized to reduce wasteful data at each memory call.

### Claim 24 (depends on 14)

The computing system of claim 14, wherein the social network graph topology has a distribution associated with each edge.

### Claim 25 (depends on 24)

The computing system of claim 24, wherein the distribution is an exponential distribution with a parameter that varies from edge to edge.

### Claim 26 (depends on 14)

The computing system of claim 14, wherein the parallel processing of each sample considers a deadline time.

### Claim 27

One or more non-transitory computer readable mediums for determining influence spread in social networks, the one or more non-transitory computer readable mediums collectively comprising computer executable instructions, that when executed, cause a computing system to at least:
generate a plurality of samples, each sample corresponding to a collection of all edge weights for a social network graph topology;
allocate the plurality of samples into at least one batch, a size of which is being determined according to a number of threads and global memory space available in a multi-processor platform;
for each batch:
parallel process the samples in that batch using the multi-processor platform to generate results corresponding to a spread of each graph node per sample in that batch;
store results of that batch in the global memory accessible to the multi-processor platform; and
compute an average spread of each node across all samples in all batches; and
determine, from the average spreads, one or more nodes having a largest spread.
