A Parallel Algorithm for Cohesive Sub-Graph Mining in Big Graphs

Alemi, Mehdi; Haghighi, Hassan

A Parallel Algorithm for Cohesive Sub-Graph Mining in Big Graphs

نویسندگان

Mehdi Alemi

Hassan Haghighi

Faculty of Computer Science and Engineering, Shahid Beh eshti University, Tehran, Iran

چکیده

Cohesive subgraph detection has an important role in many applications like search engines and biological networks. Among the cohesive subgraphs, K-Truss is getting important because of its simplicity and many usages,e.g., graph visualization and finding dense parts from the graph. Considering big graphs, parallel algorithms should be taken into account in order to get reasonable response time. In this regards, to mine K-Truss subgraphs, we have proposed a parallel algorithm in two phases. For the first phase, a concurrent method has been developed to find all the triangles from the given graph. In addition, a new data structure, called triangle vertices (TVs), has been designed to maintain a set of vertices constructing a triangle with an edge. In the second phase, iteratively, invalid edges are excluded from TVs by a parallel algorithm until no edge disobeying the K-Truss attributes is found. According to the experiments on a machine with 12 cores, using the real graphs, the performance of the proposed approach is proved against the other competitors. Moreover, by configuring different cores, the scalability of our method is presented.

کلیدواژه‌ها

Cohesive Communities

Social Networks

Parallel Processing

Triangle Counting

K-Truss