Evaluating balancing on social networks through the efficient solution of correlation clustering problems
One challenge for social network researchers is to evaluate balance in a social network. The degree of balance in a social group can be used as a tool to study whether and how this group evolves to a possible balanced state. The solution of clustering problems defined on signed graphs can be used as...
Guardado en:
Autores principales: | , , , |
---|---|
Formato: | article |
Lenguaje: | EN |
Publicado: |
Elsevier
2017
|
Materias: | |
Acceso en línea: | https://doaj.org/article/731f7de9829440968feee5f1a3ba8647 |
Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
id |
oai:doaj.org-article:731f7de9829440968feee5f1a3ba8647 |
---|---|
record_format |
dspace |
spelling |
oai:doaj.org-article:731f7de9829440968feee5f1a3ba86472021-12-02T05:01:03ZEvaluating balancing on social networks through the efficient solution of correlation clustering problems2192-440610.1007/s13675-017-0082-6https://doaj.org/article/731f7de9829440968feee5f1a3ba86472017-12-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000897https://doaj.org/toc/2192-4406One challenge for social network researchers is to evaluate balance in a social network. The degree of balance in a social group can be used as a tool to study whether and how this group evolves to a possible balanced state. The solution of clustering problems defined on signed graphs can be used as a criterion to measure the degree of balance in social networks and this measure can be obtained with the optimal solution of the correlation clustering problem, as well as a variation of it, the relaxed correlation clustering problem. However, solving these problems is no easy task, especially when large network instances need to be analyzed. In this work, we contribute to the efficient solution of both problems by developing sequential and parallel ILS metaheuristics. Then, by using our algorithms, we solve the problem of measuring the structural balance on large real-world social networks.Mario LevoratoRosa FigueiredoYuri FrotaLúcia DrummondElsevierarticle90C3505C2291D3090C59Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 5, Iss 4, Pp 467-498 (2017) |
institution |
DOAJ |
collection |
DOAJ |
language |
EN |
topic |
90C35 05C22 91D30 90C59 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 |
spellingShingle |
90C35 05C22 91D30 90C59 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Mario Levorato Rosa Figueiredo Yuri Frota Lúcia Drummond Evaluating balancing on social networks through the efficient solution of correlation clustering problems |
description |
One challenge for social network researchers is to evaluate balance in a social network. The degree of balance in a social group can be used as a tool to study whether and how this group evolves to a possible balanced state. The solution of clustering problems defined on signed graphs can be used as a criterion to measure the degree of balance in social networks and this measure can be obtained with the optimal solution of the correlation clustering problem, as well as a variation of it, the relaxed correlation clustering problem. However, solving these problems is no easy task, especially when large network instances need to be analyzed. In this work, we contribute to the efficient solution of both problems by developing sequential and parallel ILS metaheuristics. Then, by using our algorithms, we solve the problem of measuring the structural balance on large real-world social networks. |
format |
article |
author |
Mario Levorato Rosa Figueiredo Yuri Frota Lúcia Drummond |
author_facet |
Mario Levorato Rosa Figueiredo Yuri Frota Lúcia Drummond |
author_sort |
Mario Levorato |
title |
Evaluating balancing on social networks through the efficient solution of correlation clustering problems |
title_short |
Evaluating balancing on social networks through the efficient solution of correlation clustering problems |
title_full |
Evaluating balancing on social networks through the efficient solution of correlation clustering problems |
title_fullStr |
Evaluating balancing on social networks through the efficient solution of correlation clustering problems |
title_full_unstemmed |
Evaluating balancing on social networks through the efficient solution of correlation clustering problems |
title_sort |
evaluating balancing on social networks through the efficient solution of correlation clustering problems |
publisher |
Elsevier |
publishDate |
2017 |
url |
https://doaj.org/article/731f7de9829440968feee5f1a3ba8647 |
work_keys_str_mv |
AT mariolevorato evaluatingbalancingonsocialnetworksthroughtheefficientsolutionofcorrelationclusteringproblems AT rosafigueiredo evaluatingbalancingonsocialnetworksthroughtheefficientsolutionofcorrelationclusteringproblems AT yurifrota evaluatingbalancingonsocialnetworksthroughtheefficientsolutionofcorrelationclusteringproblems AT luciadrummond evaluatingbalancingonsocialnetworksthroughtheefficientsolutionofcorrelationclusteringproblems |
_version_ |
1718400836108812288 |