2025 [ nach oben ]

de la Haye, Merlin; Lenzner, Pascal; Schmand‎, Daniel; Schröder‎, Nicole Network Creation Games with 2-Neighborhood MaximizationInternational Conference on Algorithms and Complexity (CIAC) 2025: 18–34
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha\) and the number of agents \(n\). Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\Omega\left(\log\left(\frac{n}{\alpha}\right)\right)\) lower bound for NE, and a tight linear bound for GE for low \(\alpha\). Keywords: Network Creation Games, Social Networks, Structure of Equilibria, Price of Anarchy, Diameter, Network Density
@inproceedings{dlHLSS2025-NCGTwoNeighborhood, abstract = {Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha\) and the number of agents \(n\). Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\Omega\left(\log\left(\frac{n}{\alpha}\right)\right)\) lower bound for NE, and a tight linear bound for GE for low \(\alpha\). Keywords: Network Creation Games, Social Networks, Structure of Equilibria, Price of Anarchy, Diameter, Network Density}, author = {de la Haye, Merlin and Lenzner, Pascal and Schmand‎, Daniel and Schröder‎, Nicole}, booktitle = {International Conference on Algorithms and Complexity (CIAC)}, editor = {Finocchi, Irene and Georgiadis, Loukas}, keywords = {CIAC danielschmand merlindelahaye nicoleschroeder pascallenzner year2025}, pages = {18–34}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Network Creation Games with 2-Neighborhood Maximization}, volume = 15680, year = 2025 }

2021 [ nach oben ]

Atzberger, Daniel; Cech, Tim; de la Haye, Merlin; Söchting, Maximilian; Scheibel, Willy; Limberger, Daniel; Döllner, Jürgen Software Forest: A Visualization of Semantic Similarities in Source Code using a Tree MetaphorProceedings of the 16th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications -- Volume 3 IVAPP 2021: 112–122
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Software visualization techniques provide effective means for program comprehension tasks as they allow developers to interactively explore large code bases. A frequently encountered task during software development is the detection of source code files of similar semantic. To assist this task we present Software Forest, a novel 2.5D software visualization that enables interactive exploration of semantic similarities within a software system, illustrated as a forest. The underlying layout results from the analysis of the vocabulary of the software documents using Latent Dirichlet Allocation and Multidimensional Scaling and therefore reflects the semantic similarity between source code files. By mapping properties of a software entity, e.g., size metrics or trend data, to visual variables encoded by various, figurative tree meshes, aspects of a software system can be displayed. This concept is complemented with implementation details as well as a discussion on applications.
@inproceedings{atzberger2021-softwareforest-ae-version, abstract = {Software visualization techniques provide effective means for program comprehension tasks as they allow developers to interactively explore large code bases. A frequently encountered task during software development is the detection of source code files of similar semantic. To assist this task we present Software Forest, a novel 2.5D software visualization that enables interactive exploration of semantic similarities within a software system, illustrated as a forest. The underlying layout results from the analysis of the vocabulary of the software documents using Latent Dirichlet Allocation and Multidimensional Scaling and therefore reflects the semantic similarity between source code files. By mapping properties of a software entity, e.g., size metrics or trend data, to visual variables encoded by various, figurative tree meshes, aspects of a software system can be displayed. This concept is complemented with implementation details as well as a discussion on applications.}, author = {Atzberger, Daniel and Cech, Tim and de la Haye, Merlin and Söchting, Maximilian and Scheibel, Willy and Limberger, Daniel and Döllner, Jürgen}, booktitle = {Proceedings of the 16th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications – Volume 3 IVAPP}, keywords = {danielatzberger daniellimberger ivapp juergendoellner maximiliansoechting merlindelahaye timcech willyscheibel year2021}, organization = {INSTICC}, pages = {112–122}, publisher = {SciTePress}, title = {Software Forest: A Visualization of Semantic Similarities in Source Code using a Tree Metaphor}, year = 2021 }