Method and apparatus for graphical processing unit (gpu) accelerated large-scale web community detection

A non-transitory computer-readable medium storing a plurality of instructions which, when executed by a graphical processing unit (GPU), cause the GPU to perform operations for large-scale web community detection, the operations comprising:

• receiving an input graph formatted into one or more first adjacency lists from a central processing unit (CPU);
• performing a first level shingling on the one or more first adjacency lists;
• sending the first level shingling to the CPU to generate an aggregate graph based upon the first level shingling;
• receiving the aggregate graph formatted into one or more second adjacency lists from the CPU;
• performing a second level shingling on the one or more second adjacency lists;
• and
• sending the second level shingling to the CPU to generate a dense sub-graph that identifies one or more web communities.

A method for large-scale web community detection using a graphical processing unit (GPU), comprising:

• receiving, by the GPU, in a global memory of the GPU an input graph formatted into one or more first adjacency lists from a central processing unit (CPU), wherein one or more boundaries between the one or more first adjacency lists is marked;
• performing, by the GPU, a first level shingling on the one or more first adjacency lists comprising a first plurality of random hash operations to generate a first plurality of different random permutations of the one or more first adjacency lists, wherein each one of the first plurality of random hash operations applies a different hash function and performing a first segmented sorting operation one each one of the first plurality of different random permutations using each one of a plurality of threads in a shared memory of the GPU in parallel;
• sending, by the GPU, the first level shingling to the CPU to generate an aggregate graph based upon the first level shingling;
• receiving, by the GPU, the aggregate graph formatted into one or more second adjacency lists from the CPU), wherein one or more boundaries between the one or more second adjacency lists is marked;
• performing, by the GPU, a second level shingling on the one or more second adjacency lists comprising a second plurality of random hash operations to generate a second plurality of different random permutations of the one or more second adjacency lists, wherein each one of the second plurality of random hash operations applies a different hash function and performing a second segmented sorting operation one each one of the second plurality of different random permutations using each one of a plurality of threads in a shared memory of the GPU in parallel;
• and
• sending, by the GPU, the second level shingling to the CPU to generate a dense sub-graph that identifies one or more web communities.