Game theory based algorithms for community detection
The problem of community detection is important as it helps in understanding the spread of information in a social network. Linkages are more likely to form between similar people, leading to the formation of some community structure which characterizes the network dynamic. The more friends the t...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/65384 |
| _version_ | 1811690945980137472 |
|---|---|
| author | Radhika Arava |
| author2 | Chen Ning |
| author_facet | Chen Ning Radhika Arava |
| author_sort | Radhika Arava |
| collection | NTU |
| description | The problem of community detection is important as it helps in understanding the spread
of information in a social network. Linkages are more likely to form between similar people,
leading to the formation of some community structure which characterizes the network dynamic.
The more friends the two people have in common, the more the influence that each person can
exercise on the other. We assume that communities capture homophily as people of the same
community share a lot of similar features and hence the people of the same community are
likely to follow the same trend. We use the concept of weighted potential games to formulate
the model and the community detection algorithms.
We propose a disjoint community detection algorithm, NashDisjoint that detects disjoint
communities in any given network, which works as good as the state of the art algorithms on
LFR Benchmarks for the mixing factors less than 0.6. We propose an overlapping community
detection algorithm NashOverlap to detect the overlapping communities in any given network.
We evaluate the algorithm NashOverlap against the state of the art algorithms so far and we find
that our algorithm works far better than the state of the art on the standard LFR benchmarks
in around 152 different scenarios, generated by varying the number of vertices, community size,
mixing factor and overlapping membership with respect to the Normalized Mutual Information
measure.
We identify and study the significant collaboration groups of DBLP datasets using our
algorithm NashOverlap. We compare our results with that of the algorithm COPRA and find
that our algorithm can give more and better insights into the dataset. |
| first_indexed | 2024-10-01T06:12:04Z |
| format | Thesis |
| id | ntu-10356/65384 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:12:04Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | ntu-10356/653842023-02-28T23:48:59Z Game theory based algorithms for community detection Radhika Arava Chen Ning School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Discrete mathematics::Algorithms The problem of community detection is important as it helps in understanding the spread of information in a social network. Linkages are more likely to form between similar people, leading to the formation of some community structure which characterizes the network dynamic. The more friends the two people have in common, the more the influence that each person can exercise on the other. We assume that communities capture homophily as people of the same community share a lot of similar features and hence the people of the same community are likely to follow the same trend. We use the concept of weighted potential games to formulate the model and the community detection algorithms. We propose a disjoint community detection algorithm, NashDisjoint that detects disjoint communities in any given network, which works as good as the state of the art algorithms on LFR Benchmarks for the mixing factors less than 0.6. We propose an overlapping community detection algorithm NashOverlap to detect the overlapping communities in any given network. We evaluate the algorithm NashOverlap against the state of the art algorithms so far and we find that our algorithm works far better than the state of the art on the standard LFR benchmarks in around 152 different scenarios, generated by varying the number of vertices, community size, mixing factor and overlapping membership with respect to the Normalized Mutual Information measure. We identify and study the significant collaboration groups of DBLP datasets using our algorithm NashOverlap. We compare our results with that of the algorithm COPRA and find that our algorithm can give more and better insights into the dataset. DOCTOR OF PHILOSOPHY (SPMS) 2015-09-07T05:51:28Z 2015-09-07T05:51:28Z 2015 2015 Thesis Radhika Arava. (2015). Game theory based algorithms for community detection. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/65384 10.32657/10356/65384 en 158 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Discrete mathematics::Algorithms Radhika Arava Game theory based algorithms for community detection |
| title | Game theory based algorithms for community detection |
| title_full | Game theory based algorithms for community detection |
| title_fullStr | Game theory based algorithms for community detection |
| title_full_unstemmed | Game theory based algorithms for community detection |
| title_short | Game theory based algorithms for community detection |
| title_sort | game theory based algorithms for community detection |
| topic | DRNTU::Science::Mathematics::Discrete mathematics::Algorithms |
| url | https://hdl.handle.net/10356/65384 |
| work_keys_str_mv | AT radhikaarava gametheorybasedalgorithmsforcommunitydetection |