Social networks: influence and network location

Among the many methods for influence maximisation, we were among the first to propose metaheuristics based on evolutionary algorithms: single-objective (2016), then multi-objective (2017, best paper award). This was followed by more efficient fitness functions and genetic operators, and a method using graph downscaling (2022) which is able to drastically scale up the case studies if the network is modular. These metaheuristics lack explainability of the results: it is not clear why a certain network node has good spreading ability, by itself or in a group. Some explanations could be found for single influencers by linking models of influence diffusion with network statistics: one's influence can be predicted well by combinations of node centrality metrics first in small synthetic networks (2020), then also in large empirical networks (2020), and there is some common pattern of influential network positions across networks. Gave a PPSN keynote on this topic (2022, slides). (Image: network of Facebook pages with top influencers marked.)

Network of Facebook pages with top influencers marked

Star constellations: network structure

Star constellations are now defined as bounded areas of the sky, but traditional astronomies around the world represented them as groups of stars, line figures, or pictographs. I digitised a dataset of constellation line figures (GitHub, .json format in progress) from scholarly literature, extending the sky cultures of the astronomical software Stellarium to over 1800 constellations from 56 cultures on all continents (with the set still growing). The network structure of these constellations (essentially spatial graphs in spherical coordinates) is analysed in The network signature of constellation line figures. I show that the constellations cluster by network typology into six clusters, and that cultures also cluster into three clusters by the network typology of their constellations. Finally, I show that there is great diversity among the networks drawn by the various cultures around the same root star, and that the line figures are similar only in a minority of sky regions characterised by linear star patterns.(Image: the reconstructed constellation Golden Feline of the Inca in South America.)

Here is a letter I wrote in response to a young student asking about why and how constellations were created.

The constellation Golden Feline of the Inca in South America