labelrank-communities-openmp
Comparing approaches for community detection using OpenMP-based LabelRank algorithm.
Science Score: 41.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
○DOI references
-
✓Academic publication links
Links to: arxiv.org, zenodo.org -
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (7.6%) to scientific vocabulary
Keywords
Repository
Comparing approaches for community detection using OpenMP-based LabelRank algorithm.
Basic Info
Statistics
- Stars: 1
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 1
Topics
Metadata Files
README.md
Comparing approaches for community detection using OpenMP-based LabelRank algorithm.
LabelRank is an algorithm for detecting communities in graphs. Community detection helps us understand the natural divisions in a network in an unsupervised manner. It is used in e-commerce for customer segmentation and advertising, in communication networks for multicast routing and setting up of mobile networks, and in healthcare for epidemic causality, setting up health programmes, and fraud detection is hospitals. Community detection is an NP-hard problem, but heuristics exist to solve it (such as this). LabelRank is an iterative algorithm that is based on the concept of propagation of weighted labels on a weighted (directed) network, where the highest weight label determines the community membership of each vertex.
Our implementation of LabelRank differs from the original algorithm in that there is a fixed upper limit on the number of labels per vertex (labelset capacity). Therefore we do not use the cutoff operator (which removes low-weighted labels), but instead trim-off labels if they do not fit within labelset capacity. Labels are sorted by weight such that only low-weighted labels are eliminated. The input data used for each experiment given below is available from the SuiteSparse Matrix Collection. All experiments are done with guidance from Prof. Kishore Kothapalli and Prof. Dip Sankar Banerjee.
Adjusting OpenMP schedule
In this experiment (adjust-schedule, main), we attempt performing the
OpenMP-based LabelRank algorithm with all different schedule kinds
(static, dynamic, guided, and auto), which adjusting the chunk size
from 1 to 65536 in multiples of 2. In all cases, we use a total of 12 threads.
We choose the LabelRank parameters as inflation = 1.5 and conditionalUpdate = 0.5.
In addition, we use a fixed labelset capacity of 4, and run the algorithm
for exactly 10 iterations. We measure the time taken for the computation
(performed 5 times for averaging), and measure the modularity score (one
of the ways to measure quality of communities). This is repeated for seventeen
different graphs.
From the results, we observe that a dynamic schedule kind, with a chunk
size of 1024 appears to perform the best in most cases. Exceptions include
soc-Epinions1 graphs, where using a chunk size of 256 would be a better
choice; and web-Google, where using a guided schedule kind with chunk size
of 256 would be better. Note that these paramter choices might differ if a
different labelset capacity, or different LabelRank parameters are used.
References
- LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation
- LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
- SuiteSparse Matrix Collection
Owner
- Name: puzzlef
- Login: puzzlef
- Kind: organization
- Website: https://puzzlef.github.io/
- Repositories: 10
- Profile: https://github.com/puzzlef
A summary of experiments.
Citation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: Sahu
given-names: Subhajit
orcid: https://orcid.org/0000-0001-5140-6578
title: "puzzlef/labelrank-openmp-adjust-schedule: Effect of adjusting schedule in OpenMP-based LabelRank algorithm for community detection"
version: 1.0.0
doi: 10.5281/zenodo.6838228
date-released: 2022-07-15
GitHub Events
Total
- Push event: 1
Last Year
- Push event: 1
Issues and Pull Requests
Last synced: 11 months ago
All Time
- Total issues: 0
- Total pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Total issue authors: 0
- Total pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0