A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees
Several synchronous applications are based on the graph-structured data; among them, a very important application of this kind is community detection. Since the number and size of the networks modeled by graphs grow larger and larger, some level of parallelism needs to be used, to reduce the computa...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8636962/ |
| _version_ | 1818556898759147520 |
|---|---|
| author | Stavros Souravlas Angelo Sifaleras Stefanos Katsavounis |
| author_facet | Stavros Souravlas Angelo Sifaleras Stefanos Katsavounis |
| author_sort | Stavros Souravlas |
| collection | DOAJ |
| description | Several synchronous applications are based on the graph-structured data; among them, a very important application of this kind is community detection. Since the number and size of the networks modeled by graphs grow larger and larger, some level of parallelism needs to be used, to reduce the computational costs of such massive applications. Social networking sites allow users to manually categorize their friends into social circles (referred to as lists on Facebook and Twitter), while users, based on their interests, place themselves into groups of interest. However, the community detection and is a very effortful procedure, and in addition, these communities need to be updated very often, resulting in more effort. In this paper, we combine parallel processing techniques with a typical data structure like threaded binary trees to detect communities in an efficient manner. Our strategy is implemented over weighted networks with irregular topologies and it is based on a stepwise path detection strategy, where each step finds a link that increases the overall strength of the path being detected. To verify the functionality and parallelism benefits of our scheme, we perform experiments on five real-world data sets: Facebook<sup>®</sup>, Twitter<sup>®</sup>, Google+<sup>®</sup>, Pokec, and LiveJournal. |
| first_indexed | 2024-12-13T23:53:10Z |
| format | Article |
| id | doaj.art-839d834198e848d8aa90f21448db6bac |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-13T23:53:10Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-839d834198e848d8aa90f21448db6bac2022-12-21T23:26:42ZengIEEEIEEE Access2169-35362019-01-017204992051910.1109/ACCESS.2019.28977838636962A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary TreesStavros Souravlas0https://orcid.org/0000-0002-9602-2663Angelo Sifaleras1https://orcid.org/0000-0002-5696-7021Stefanos Katsavounis2Department of Applied Informatics, University of Macedonia, Thessaloniki, GreeceDepartment of Applied Informatics, University of Macedonia, Thessaloniki, GreeceDepartment of Production and Management Engineering, Democritus University of Thrace, Xanthi, GreeceSeveral synchronous applications are based on the graph-structured data; among them, a very important application of this kind is community detection. Since the number and size of the networks modeled by graphs grow larger and larger, some level of parallelism needs to be used, to reduce the computational costs of such massive applications. Social networking sites allow users to manually categorize their friends into social circles (referred to as lists on Facebook and Twitter), while users, based on their interests, place themselves into groups of interest. However, the community detection and is a very effortful procedure, and in addition, these communities need to be updated very often, resulting in more effort. In this paper, we combine parallel processing techniques with a typical data structure like threaded binary trees to detect communities in an efficient manner. Our strategy is implemented over weighted networks with irregular topologies and it is based on a stepwise path detection strategy, where each step finds a link that increases the overall strength of the path being detected. To verify the functionality and parallelism benefits of our scheme, we perform experiments on five real-world data sets: Facebook<sup>®</sup>, Twitter<sup>®</sup>, Google+<sup>®</sup>, Pokec, and LiveJournal.https://ieeexplore.ieee.org/document/8636962/Community detectionparallel algorithmsbinary treessocial circles |
| spellingShingle | Stavros Souravlas Angelo Sifaleras Stefanos Katsavounis A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees IEEE Access Community detection parallel algorithms binary trees social circles |
| title | A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees |
| title_full | A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees |
| title_fullStr | A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees |
| title_full_unstemmed | A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees |
| title_short | A Parallel Algorithm for Community Detection in Social Networks, Based on Path Analysis and Threaded Binary Trees |
| title_sort | parallel algorithm for community detection in social networks based on path analysis and threaded binary trees |
| topic | Community detection parallel algorithms binary trees social circles |
| url | https://ieeexplore.ieee.org/document/8636962/ |
| work_keys_str_mv | AT stavrossouravlas aparallelalgorithmforcommunitydetectioninsocialnetworksbasedonpathanalysisandthreadedbinarytrees AT angelosifaleras aparallelalgorithmforcommunitydetectioninsocialnetworksbasedonpathanalysisandthreadedbinarytrees AT stefanoskatsavounis aparallelalgorithmforcommunitydetectioninsocialnetworksbasedonpathanalysisandthreadedbinarytrees AT stavrossouravlas parallelalgorithmforcommunitydetectioninsocialnetworksbasedonpathanalysisandthreadedbinarytrees AT angelosifaleras parallelalgorithmforcommunitydetectioninsocialnetworksbasedonpathanalysisandthreadedbinarytrees AT stefanoskatsavounis parallelalgorithmforcommunitydetectioninsocialnetworksbasedonpathanalysisandthreadedbinarytrees |