Data Infrastructure and Method for Estimating Influence Spread in Social Networks
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.
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.
2 . 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.
3 . The method of claim 1 , further comprising outputting the results to a social media intelligence application.
4 . The method of claim 1 , wherein the multi-processor platform is a graphics processing unit (GPU).
5 . The method of claim 1 , wherein the multi-processor platform is a multi-core processor.
6 . The method of claim 1 , wherein each sample is processed in a thread by applying a Naïve Sampling algorithm.
7 . The method of claim 1 , wherein each sample is processed in a thread by applying a Cohen's Neighborhood Size Estimation algorithm.
8 . 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.
9 . 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.
10 . 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.
11 . The method of claim 1 , wherein the social network graph topology has a distribution associated with each edge.
12 . The method of claim 11 , wherein the distribution is an exponential distribution with a parameter that varies from edge to edge.
13 . The method of claim 1 , wherein the parallel processing of each sample considers a deadline time.
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.
15 . The computing system of claim 14 , wherein the multi-processor platform comprises a graphics processing unit (GPU).
16 . 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.
17 . The computing system of claim 14 wherein the central processor system is configured to output the results to a social media intelligence application.
18 . The computing system of claim 14 , wherein the multi-processor platform is a multi-core processor.
19 . The computing system of claim 14 , wherein each sample is processed in a thread by applying a Naïve Sampling algorithm.
20 . The computing system of claim 14 , wherein each sample is processed in a thread by applying a Cohen's Neighborhood Size Estimation algorithm.
21 . 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.
22 . 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.
23 . 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.
24 . The computing system of claim 14 , wherein the social network graph topology has a distribution associated with each edge.
25 . The computing system of claim 24 , wherein the distribution is an exponential distribution with a parameter that varies from edge to edge.
26 . The computing system of claim 14 , wherein the parallel processing of each sample considers a deadline time.
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.