UNIVERSIDADEFEDERALDORIOGRANDEDOSUL INSTITUTODEINFORMÁTICA PROGRAMADEPÓS-GRADUAÇÃOEMCOMPUTAÇÃO DIEGOVRAGUENOBLE The Role of Heterogeneity in Social Problem-Solving Thesispresentedinpartialfulfillment oftherequirementsforthedegreeof DoctorofComputerScience Advisor:Prof.Dr.LuísdaCunhaLamb Coadvisor:Prof.Dr.RicardoMatsumuraAraújo PortoAlegre December2017 CIP—CATALOGING-IN-PUBLICATION Noble,DiegoVrague TheRoleofHeterogeneityinSocialProblem-Solving/Diego VragueNoble.–PortoAlegre: PPGCdaUFRGS,2017. 73f.: il. Thesis (Ph.D.) – Universidade Federal do Rio Grande do Sul. ProgramadePós-GraduaçãoemComputação,PortoAlegre,BR– RS, 2017. Advisor: Luís da Cunha Lamb; Coadvisor: Ricardo MatsumuraAraújo. 1.Computationalsocialsystems. 2.Computationalsocialsci- ence. 3. Social computing. I. Lamb, Luís da Cunha. II. Araújo, RicardoMatsumura. III.Título. UNIVERSIDADEFEDERALDORIOGRANDEDOSUL Reitor: Prof.RuiVicenteOppermann Vice-Reitora: Profa.JaneFragaTutikian Pró-ReitordePós-Graduação: Prof.CelsoGiannettiLoureiroChaves DiretoradoInstitutodeInformática: Profa.CarlaMariaDalSassoFreitas CoordenadordoPPGC:Prof.JoãoLuizDihlComba Bibliotecária-chefedoInstitutodeInformática: BeatrizReginaBastosHaro “The roots of education are bitter, but the fruit is sweet.” — ARISTOTLE AGRADECIMENTOS Agradeço aos meus orientadores, Prof. Ricardo e Prof. Lamb, por todo o esforço e apoio. Tenho muitíssimo orgulho e gratidão por ter sido aprendiz de vocês durante este processo. Agradeço aos funcionários do Instituto de Informática e do Programa de Pós- graduaçãodaUFRGSpelaprestatividadeededicação. SougratoaoLuisOtávio,àSilvâ- nia,àElisianeeaosdemaisfuncionáriosdoinstituto. Agradeço aos colegas de laboratório pelas críticas e sugestões valiosas. Ao Már- cio, ao Rafael, à Fabiane, ao Marlo, ao Marcelo, à Jéssica, ao Felipe eu afirmo que foi umaenormesatisfaçãotervocêscomocolegas. ABSTRACT This thesis reviews and investigates social problem-solving with a particular focus on ar- tificial and heterogeneous systems. More specifically, we not only compile and compre- hensively examine recent research results, but also discuss future directions in the study of such heterogeneous complex systems. Given their complex nature, such systems of- ten defy analyses. Even computationally simple models can behave unpredictably after a few iterations. Therefore, one central issue in Social Computing is to devise models of social interaction that are amenable to investigation. This way, one can understand the complexrelationshipsamongthecomponentsandtheoutcomeofthesocialprocess. This thesis surveys scientific inquiries concerned with fundamental aspects in social problem- solving systems and their impact in ability and performance of such systems. These aspects include modeling, communication structure and individual problem-solver traits. This thesis also reports the student endeavour during the period of research and summa- rizes several already published contributions. Among them there is (i) the study of gen- eral frameworks for the study of social problem-solving, (ii) the investigation of the role of centrality in individual and collective outcomes, and (iii) the exploration of heteroge- neous models of social problem-solving. These three points, in an integrated perspective underpintheunderstandingofnetworkandcommunicationstructures,adjustthestrategic systems’ composition, and exploit problems’ structures and patterns in social problem- solvingsystems. Keywords: Computational social systems. computational social science. social comput- ing. SistemasHeterogêneosdeResoluçãoSocialdeProblemas RESUMO Metódos analíticos de investigação são usualmente ineficazes para sistemas computaci- onais sociais já que apenas algumas iterações do sistema já são suficientes para que o sistema se torne imprevisível. Portanto, uma das principais questões na Computação So- cial é o desenvolvimento de modelos sociais passíveis de investigação. Assim é possível quesecompreendaorelacionamentocomplexoentreoscomponentesdesistemassociais computacionais e o resultado. Este aspectos incluem a modelagem, a estrutura de comu- nicação e características individuais do agentes envolvidos na resolução dos problemas. doprocessosocial. Estateseexplorasistemascomputacionaisderesoluçãodeproblemas com foco em sistemas artificiais e heterogêneos. Nela é feita uma compilação extensiva da literatura relacionada em sistemas complexos onde as contribuições do candidato são expostas dentro de contextos específicos da área. Entre elas está o estudo de modelos abstratos e gerais de resolução social de problemas, a investigação do impacto da centra- lidadenoresultadoindividualecoletivo,aanáliseexperimentaldemodelosheterogêneos de resolução social de problemas. Quando integradas, estas contribuições reforçam o en- tendimento sobre a importância da rede e das estruturas de comunicação, a composição estratégica do sistema, a estrutura do problema e possíveis padrões gerais na resolução socialdeproblemas. Palavras-chave: SistemasSociaisComputacionais,ComputaçãoSocial,InteligênciaAr- tificial. LISTOFABBREVIATIONSANDACRONYMS DSR DynamicSearchRange FIPS Fully-InformedParticleSwarm LF Lazer-FreidmanModel MN MemeticNetworks NBA Barabási-Albertgenerativenetworkmodel PSO ParticleSwarmOptimization CONTENTS LISTOFFIGURES.........................................................................................................9 LISTOFTABLES.........................................................................................................10 1INTRODUCTION.......................................................................................................11 2ONTHEFEASIBILITYOFAGENERALFRAMEWORKFORCOMPU- TATIONALSOCIALPROBLEM-SOLVING.................................................17 2.1 Methods....................................................................................................................17 2.1.1 ParticleSwarmOptimization.................................................................................17 2.1.2 MemeticNetworks.................................................................................................19 2.1.3 AnHeterogeneousFrameworkComposedbyParticlesandMemeticNodes.......20 2.1.4 ExperimentalSetup................................................................................................23 2.2 Results......................................................................................................................25 2.3 Discussion................................................................................................................26 3THEIMPACTOFCENTRALITYINCOMPUTATIONALSOCIALPROBLEM- SOLVING.............................................................................................................30 3.1 Methods....................................................................................................................30 3.2 Results......................................................................................................................37 3.3 Discussion................................................................................................................39 4HETEROGENEOUSMODELSCOMPUTATIONALOFSOCIALPROBLEM- SOLVING.............................................................................................................44 4.1 Methods....................................................................................................................45 4.2 DissociatingExploitationfromExploration.........................................................49 4.3 Diversity,StrategyandNetworkEfficiency..........................................................51 4.4 Discussion................................................................................................................54 5CONCLUSIONS.........................................................................................................56 REFERENCES...............................................................................................................58 APPENDIXA—RESUMODATESE........................................................................65 A.1 PrincipaisObjetivoseTrabalhosPublicados......................................................66 A.2 EstudodeViabilidadedeumModeloGeraldeResoluçãoSocialdeProblemas66 A.3 ARelevânciadaCentralidadenaResoluçãoSocialdeProblemas....................67 A.3.1 MétodosePrincipaisResultados..........................................................................68 A.4 ModelosHeterogêneosdeResoluçãoSocialdeProblemas................................68 A.4.1 MétodosePrincipaisResultados..........................................................................68 A.5 ConclusõesGerais..................................................................................................69 LISTOFFIGURES Figure2.1 The 6×5 periodic grid graph used as the network topology in our ex- periments..................................................................................................................25 Figure2.2 Theevolutionofthebestsolutionfoundbyallalgorithmsaveragedover the 50 independent trials. Our heterogeneous model with the population dis- tribution of half particles and half memetic nodes presents better results for the Ackley and Rastrigin Functions after one thousand iterations. In the other cases, the heterogeneous model was equivalent to PSO and FIPS. Both axis areinlogarithmicscale............................................................................................28 Figure2.3 Solution quality distribution extracted the 30 individuals from the last generation of all the 50 runs. The heterogeneous model presented the highest solutiondiversityamongallaswehypothesized.....................................................29 Figure3.1 Networks generated by the Barabási-Albert model where new nodes connect to m = 2 following a preferential attachment mechanism of connec- tion. The network sizes were 16 a, 64 b, and 144 c. The node size in these picturesisdirectlyproportionaltoitsdegree...........................................................31 Figure3.2 Sampletrialsdepictingaclosetozerocorrelation(FIPS,F4,population size 144), a negative correlation (-0.72, FIPS, F1, population size 144) and a positivecorrelation(0.79,DSR,F5,populationsize144)respectivelytop-down..39 Figure4.1 Sample problem instance: The peak is represented by the light green regionwhilethenoiseisrepresentedindarkergreen..............................................46 Figure4.2 Probability of finding the peak for various radius sizes in our Ring ModelandintheMason&Wattsmodel.................................................................50 Figure4.3 Averagescoresovertimefordifferentpopulationsizesandmodels............52 Figure4.4 Rounds before finding the peak (solution) for the most, median, and least central node in: (a) Static Homogeneous with radius 8, and the (b) Dy- namicRandommodel..............................................................................................54 FigureA.1 Convergência dos modelos para a melhor solução em diferentes mod- elos para uma média de 50 execuções independentes, cada execução limitada a 100000 iterações. A população heterogênea é composta de metade partícu- las do modelo de enxame (PSO) e o resto de indivíduos do modelo de Redes Meméticas................................................................................................................71 FigureA.2 Exemplo de instância de otimização: a solução ótima está localizada na região mais clara enquanto que a região escura representa o ruído. Cada ponto (x,y) do espaço de busca representa uma solução cujo valor objetivo da funçãoestáassociadoàcornafigura.......................................................................73 FigureA.3 Probabilidade de encontrar a solução ótima para tamanhos de raios variadosnonossomodeloenomodelooriginaldeMasoneWatts........................73 LISTOFTABLES Table1.1 Publishedworks..............................................................................................16 Table2.1 BenchmarkFunctions......................................................................................24 Table3.1 Pearson’sCorrelationBetweenIndividualGlobalContributionandCen- trality........................................................................................................................41 Table3.2 Pearson’sCorrelationBetweenIndividualLocalContributionandCentrality.42 Table3.3 AveragedStandardDeviationofIndividuals’Contributions..........................43 Table4.1 Probabilities of finding the peak for efficient (decentralized) and ineffi- cient(centralized)networks.....................................................................................53 TableA.1 CorrelaçãodePearsonentreacontribuiçãoindividualaocoletivoedifer- entesmétricasdecentralidade..................................................................................72 TableA.2 Probabilidades de encontrar a solução ótima para redes eficientes (de- scentralizadas)eredesineficientes(centralizadas)..................................................72