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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Mario Levorato, Rosa Figueiredo, Yuri Frota, Lúcia Drummond
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