Evaluating Methods for Efficient Community Detection in Social Networks
Exploring a community is an important aspect of social network analysis because it can be seen as a crucial way to decompose specific graphs into smaller graphs based on interactions between users. The process of discovering common features between groups of users, entitled “community detection”, is...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-04-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/13/5/209 |
| _version_ | 1797499095494950912 |
|---|---|
| author | Andreas Kanavos Yorghos Voutos Foteini Grivokostopoulou Phivos Mylonas |
| author_facet | Andreas Kanavos Yorghos Voutos Foteini Grivokostopoulou Phivos Mylonas |
| author_sort | Andreas Kanavos |
| collection | DOAJ |
| description | Exploring a community is an important aspect of social network analysis because it can be seen as a crucial way to decompose specific graphs into smaller graphs based on interactions between users. The process of discovering common features between groups of users, entitled “community detection”, is a fundamental feature for social network analysis, wherein the vertices represent the users and the edges their relationships. Our study focuses on identifying such phenomena on the Twitter graph of posts and on determining communities, which contain users with similar features. This paper presents the evaluation of six established community-discovery algorithms, namely Breadth-First Search, CNM, Louvain, MaxToMin, Newman–Girvan and Propinquity Dynamics, in terms of four widely used graphs and a collection of data fetched from Twitter about man-made and physical data. Furthermore, the size of each community, expressed as a percentage of the total number of vertices, is identified for the six particular algorithms, and corresponding results are extracted. In terms of user-based evaluation, we indicated to some students the communities that were extracted by every algorithm, with a corresponding user and their tweets in the grouping and considered three different alternatives for the extracted communities: “dense community”, “sparse community” and “in-between”. Our findings suggest that the community-detection algorithms can assist in identifying dense group of users. |
| first_indexed | 2024-03-10T03:42:33Z |
| format | Article |
| id | doaj.art-78e5d18e07ee4d1d9f058a7187f32982 |
| institution | Directory Open Access Journal |
| issn | 2078-2489 |
| language | English |
| last_indexed | 2024-03-10T03:42:33Z |
| publishDate | 2022-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj.art-78e5d18e07ee4d1d9f058a7187f329822023-11-23T11:29:42ZengMDPI AGInformation2078-24892022-04-0113520910.3390/info13050209Evaluating Methods for Efficient Community Detection in Social NetworksAndreas Kanavos0Yorghos Voutos1Foteini Grivokostopoulou2Phivos Mylonas3Department of Digital Media and Communication, Ionian University, 28100 Kefalonia, GreeceDepartment of Informatics, Ionian University, 49100 Corfu, GreeceComputer Engineering and Informatics Department, University of Patras, 26504 Patras, GreeceDepartment of Informatics, Ionian University, 49100 Corfu, GreeceExploring a community is an important aspect of social network analysis because it can be seen as a crucial way to decompose specific graphs into smaller graphs based on interactions between users. The process of discovering common features between groups of users, entitled “community detection”, is a fundamental feature for social network analysis, wherein the vertices represent the users and the edges their relationships. Our study focuses on identifying such phenomena on the Twitter graph of posts and on determining communities, which contain users with similar features. This paper presents the evaluation of six established community-discovery algorithms, namely Breadth-First Search, CNM, Louvain, MaxToMin, Newman–Girvan and Propinquity Dynamics, in terms of four widely used graphs and a collection of data fetched from Twitter about man-made and physical data. Furthermore, the size of each community, expressed as a percentage of the total number of vertices, is identified for the six particular algorithms, and corresponding results are extracted. In terms of user-based evaluation, we indicated to some students the communities that were extracted by every algorithm, with a corresponding user and their tweets in the grouping and considered three different alternatives for the extracted communities: “dense community”, “sparse community” and “in-between”. Our findings suggest that the community-detection algorithms can assist in identifying dense group of users.https://www.mdpi.com/2078-2489/13/5/209CNM algorithmcommunity detectiongraph miningLouvain algorithmMaxToMinmodularity |
| spellingShingle | Andreas Kanavos Yorghos Voutos Foteini Grivokostopoulou Phivos Mylonas Evaluating Methods for Efficient Community Detection in Social Networks Information CNM algorithm community detection graph mining Louvain algorithm MaxToMin modularity |
| title | Evaluating Methods for Efficient Community Detection in Social Networks |
| title_full | Evaluating Methods for Efficient Community Detection in Social Networks |
| title_fullStr | Evaluating Methods for Efficient Community Detection in Social Networks |
| title_full_unstemmed | Evaluating Methods for Efficient Community Detection in Social Networks |
| title_short | Evaluating Methods for Efficient Community Detection in Social Networks |
| title_sort | evaluating methods for efficient community detection in social networks |
| topic | CNM algorithm community detection graph mining Louvain algorithm MaxToMin modularity |
| url | https://www.mdpi.com/2078-2489/13/5/209 |
| work_keys_str_mv | AT andreaskanavos evaluatingmethodsforefficientcommunitydetectioninsocialnetworks AT yorghosvoutos evaluatingmethodsforefficientcommunitydetectioninsocialnetworks AT foteinigrivokostopoulou evaluatingmethodsforefficientcommunitydetectioninsocialnetworks AT phivosmylonas evaluatingmethodsforefficientcommunitydetectioninsocialnetworks |