An approximate algorithm for maximizing modularity by estimating the domain of influence
As social networks grow, they become more and more complex and analyzing them becomes complicated. One way to reduce this complexity is to divide the network into subnets, which are also called communities. Dividing social networks into desirable communities can help the analysts and experts to unde...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Isfahan
2022-09-01
|
| Series: | هوش محاسباتی در مهندسی برق |
| Subjects: | |
| Online Access: | https://isee.ui.ac.ir/article_25856_ab9d50db732166f473b9918d5624c22c.pdf |
| _version_ | 1797807001564086272 |
|---|---|
| author | Seyfollah Soleimani Rouhollah Javadpour Boroujeni |
| author_facet | Seyfollah Soleimani Rouhollah Javadpour Boroujeni |
| author_sort | Seyfollah Soleimani |
| collection | DOAJ |
| description | As social networks grow, they become more and more complex and analyzing them becomes complicated. One way to reduce this complexity is to divide the network into subnets, which are also called communities. Dividing social networks into desirable communities can help the analysts and experts to understand the behavior and function of the networks. Community detection in networks is a challenging topic in network science and various methods have been proposed for that. Modularity maximization is one of the state-of-the-art methods suggested for community detection. Modularity maximization is an NP-hard problem meaning that no polynomial-time algorithm exists that could solve the problem optimally unless P=NP. One group of approaches that could solve such problems is the approximate algorithms. Identifying the influential nodes has many important applications in social networks. This technique could also be used in community detection. To maximize the modularity, in this paper, we propose approximate algorithms based on identifying the influential nodes and their influence domain. We used the concept of scale-free networks to prove the approximate factor. Experiments on real-world networks show that the proposed algorithm can compete with the state-of-the-art methods of community detection algorithms. |
| first_indexed | 2024-03-13T06:15:57Z |
| format | Article |
| id | doaj.art-cdd78fb287ca464281e85401b9b6f76d |
| institution | Directory Open Access Journal |
| issn | 2821-0689 |
| language | English |
| last_indexed | 2024-03-13T06:15:57Z |
| publishDate | 2022-09-01 |
| publisher | University of Isfahan |
| record_format | Article |
| series | هوش محاسباتی در مهندسی برق |
| spelling | doaj.art-cdd78fb287ca464281e85401b9b6f76d2023-06-11T04:21:42ZengUniversity of Isfahanهوش محاسباتی در مهندسی برق2821-06892022-09-011338710010.22108/isee.2021.120798.131525856An approximate algorithm for maximizing modularity by estimating the domain of influenceSeyfollah Soleimani0Rouhollah Javadpour Boroujeni1Department of Computer Engineering, Faculty of Engineering, Arak University, Arak, IranDepartment of Computer Engineering, Faculty of Engineering, Arak University, Arak, IranAs social networks grow, they become more and more complex and analyzing them becomes complicated. One way to reduce this complexity is to divide the network into subnets, which are also called communities. Dividing social networks into desirable communities can help the analysts and experts to understand the behavior and function of the networks. Community detection in networks is a challenging topic in network science and various methods have been proposed for that. Modularity maximization is one of the state-of-the-art methods suggested for community detection. Modularity maximization is an NP-hard problem meaning that no polynomial-time algorithm exists that could solve the problem optimally unless P=NP. One group of approaches that could solve such problems is the approximate algorithms. Identifying the influential nodes has many important applications in social networks. This technique could also be used in community detection. To maximize the modularity, in this paper, we propose approximate algorithms based on identifying the influential nodes and their influence domain. We used the concept of scale-free networks to prove the approximate factor. Experiments on real-world networks show that the proposed algorithm can compete with the state-of-the-art methods of community detection algorithms.https://isee.ui.ac.ir/article_25856_ab9d50db732166f473b9918d5624c22c.pdfapproximate algorithmcommunity detectionreverse influence sampling (ris) frameworksocial networksinfluential nodesmodularity |
| spellingShingle | Seyfollah Soleimani Rouhollah Javadpour Boroujeni An approximate algorithm for maximizing modularity by estimating the domain of influence هوش محاسباتی در مهندسی برق approximate algorithm community detection reverse influence sampling (ris) framework social networks influential nodes modularity |
| title | An approximate algorithm for maximizing modularity by estimating the domain of influence |
| title_full | An approximate algorithm for maximizing modularity by estimating the domain of influence |
| title_fullStr | An approximate algorithm for maximizing modularity by estimating the domain of influence |
| title_full_unstemmed | An approximate algorithm for maximizing modularity by estimating the domain of influence |
| title_short | An approximate algorithm for maximizing modularity by estimating the domain of influence |
| title_sort | approximate algorithm for maximizing modularity by estimating the domain of influence |
| topic | approximate algorithm community detection reverse influence sampling (ris) framework social networks influential nodes modularity |
| url | https://isee.ui.ac.ir/article_25856_ab9d50db732166f473b9918d5624c22c.pdf |
| work_keys_str_mv | AT seyfollahsoleimani anapproximatealgorithmformaximizingmodularitybyestimatingthedomainofinfluence AT rouhollahjavadpourboroujeni anapproximatealgorithmformaximizingmodularitybyestimatingthedomainofinfluence AT seyfollahsoleimani approximatealgorithmformaximizingmodularitybyestimatingthedomainofinfluence AT rouhollahjavadpourboroujeni approximatealgorithmformaximizingmodularitybyestimatingthedomainofinfluence |