Modeling and analyzing user (selfish) behavior in routing and social networks

Elias Koutsoupias and Katia Papakonstantinopoulou. Contention issues in congestion games. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 623--635, Warwick, UK, July 2012.

Pdf Presentation

Abstract

We study time-dependent strategies for playing congestion games. The players can time their participation in the game with the hope that fewer players will compete for the same resources. We study two models: the boat model, in which the latency of a player is influenced only by the players that start at the same time, and the conveyor belt model in which the latency of a player is affected by the players that share the system, even if they started earlier or later; unlike standard congestion games, in these games the order of the edges in the paths affect the latency of the players. We characterize the symmetric Nash equilibria of the games with affine latencies of networks of parallel links in the boat model and we bound their price of anarchy and stability. For the conveyor belt model, we characterize the symmetric Nash equilibria of two players on parallel links. We also show that the games of the boat model are themselves congestion games. The same is true for the games of two players for the conveyor belt model; however, for this model the games of three or more players are not in general congestion games and may not have pure equilibria.

Keywords: Algorithmic game theory, price of anarchy, congestion games, contention.


Bib

@inproceedings{DBLP:conf/icalp/KoutsoupiasP12,
  author    = {Elias Koutsoupias and
               Katia Papakonstantinopoulou},
  title     = {Contention Issues in Congestion Games},
  booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
               {ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {II}},
  pages     = {623--635},
  year      = {2012},
  crossref  = {DBLP:conf/icalp/2012-2},
  url       = {http://dx.doi.org/10.1007/978-3-642-31585-5_55},
  doi       = {10.1007/978-3-642-31585-5_55},
  timestamp = {Tue, 03 Jul 2012 08:00:58 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/icalp/KoutsoupiasP12},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@proceedings{DBLP:conf/icalp/2012-2,
  editor    = {Artur Czumaj and
               Kurt Mehlhorn and
               Andrew M. Pitts and
               Roger Wattenhofer},
  title     = {Automata, Languages, and Programming - 39th International Colloquium,
               {ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {II}},
  series    = {Lecture Notes in Computer Science},
  volume    = {7392},
  publisher = {Springer},
  year      = {2012},
  url       = {http://dx.doi.org/10.1007/978-3-642-31585-5},
  doi       = {10.1007/978-3-642-31585-5},
  isbn      = {978-3-642-31584-8},
  timestamp = {Tue, 03 Jul 2012 08:00:29 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/icalp/2012-2},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}
 
Panagiotis Liakos and Katia Papakonstantinopoulou. On the Impact of Social Cost in Opinion Dynamics. In 10th International AAAI Conference on Web and Social Media (ICWSM), Cologne, Germany, May 2016.

Pdf Presentation Poster

Abstract

We study the formation of opinions in a social context. It has been observed that when in a social environment people often average their opinion with their friends’ opinions so as to highlight their common features. We analyze a popular social network and verify that social interaction indeed results in influence on opinions among the participants. Moreover we create instances of the network using real data and, based on the game theory framework, we experimentally show that the repeated averaging process results to Nash equilibria which are illustrative of how users really behave.

Keywords: Opinion dynamics, Nash equilibria, experimental evaluation.


Bib

@inproceedings{DBLP:conf/icwsm/LiakosP16,
  author    = {Panagiotis Liakos and
               Katia Papakonstantinopoulou},
  title     = {On the Impact of Social Cost in Opinion Dynamics},
  booktitle = {Proceedings of the Tenth International Conference on Web and Social
               Media, Cologne, Germany, May 17-20, 2016.},
  pages     = {631--634},
  year      = {2016},
  crossref  = {DBLP:conf/icwsm/2016},
  url       = {http://www.aaai.org/ocs/index.php/ICWSM/ICWSM16/paper/view/13139},
  timestamp = {Sun, 22 May 2016 11:02:56 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/icwsm/LiakosP16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@proceedings{DBLP:conf/icwsm/2016,
  title     = {Proceedings of the Tenth International Conference on Web and Social
               Media, Cologne, Germany, May 17-20, 2016},
  publisher = {{AAAI} Press},
  year      = {2016},
  url       = {http://www.aaai.org/Library/ICWSM/icwsm16contents.php},
  isbn      = {978-1-57735-758-2},
  timestamp = {Sun, 22 May 2016 11:02:56 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/icwsm/2016},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}
Panagiotis Liakos, Katia Papakonstantinopoulou, Michael Sioutis, Konstantinos Tsakalozos and Alex Delis. Pinpointing Influence in Pinterest. In 2nd International Workshop on Social Influence Analysis, 25th International Joint Conference on Artificial Intelligence (IJCAI), New York, United States, July 2016.

Pdf Presentation

Abstract

The success of most applications that run on top of a social network infrastructure is due to the social ties among their users; the users can get informed about the activity of their friends and acquaintances, and, hence, new ideas, habits, and products have the opportunity to gain popularity. Therefore, understanding the influence dynamics on social networks provides us with insights that are useful in designing efficient social network applications. In this work we focus on Pinterest, a social network that is often used to promote commercial products, and investigate the influence mechanisms in it. We examine the user indegree and PageRank as potential estimators of the number of repins and likes the user may receive. We observe that, although both measures are weakly associated with user influence in Pinterest, PageRank is much more powerful than indegree in revealing how much influential a user is.

Keywords: Influence dynamics, Pinterest, PageRank.


Bib

@inproceedings{DBLP:conf/ijcai/LiakosPSTD16,
  author    = {Panagiotis Liakos and
               Katia Papakonstantinopoulou and
               Michael Sioutis and
               Konstantinos Tsakalozos and
               Alex Delis},
  title     = {Pinpointing Influence in Pinterest},
  booktitle = {Proceedings of the 2nd International Workshop on Social Influence
               Analysis co-located with 25th International Joint Conference on Artificial
               Intelligence {(IJCAI} 2016), New York City, New York, USA, July 9,
               2016.},
  pages     = {26--37},
  year      = {2016},
  crossref  = {DBLP:conf/ijcai/2016socinf},
  url       = {http://ceur-ws.org/Vol-1622/SocInf2016_Paper3.pdf},
  timestamp = {Tue, 23 Aug 2016 15:20:51 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ijcai/LiakosPSTD16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@proceedings{DBLP:conf/ijcai/2016socinf,
  editor    = {Marcelo Gabriel Armentano and
               Ariel Monteserin and
               Jie Tang and
               Virginia Yannibelli},
  title     = {Proceedings of the 2nd International Workshop on Social Influence
               Analysis co-located with 25th International Joint Conference on Artificial
               Intelligence {(IJCAI} 2016), New York City, New York, USA, July 9,
               2016},
  series    = {{CEUR} Workshop Proceedings},
  volume    = {1622},
  publisher = {CEUR-WS.org},
  year      = {2016},
  url       = {http://ceur-ws.org/Vol-1622},
  urn       = {urn:nbn:de:0074-1622-3},
  timestamp = {Tue, 23 Aug 2016 15:20:20 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ijcai/2016socinf},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

Compact representation of large information, social and routing networks

Panagiotis Liakos, Katia Papakonstantinopoulou and Alex Delis. Memory-Optimized Distributed Graph Processing through Novel Compression Techniques. In 25th ACM International Conference on Information and Knowledge Management (CIKM), Indianapolis, United States, October 2016.

Pdf Presentation Poster

Abstract

A multitude of contemporary applications now involve graph data whose size continuously grows and this trend shows no signs of subsiding. This has caused the emergence of many distributed graph processing systems including Pregel and Apache Giraph. However, the unprecedented scale now reached by real-world graphs hardens the task of graph processing even in distributed environments and the current memory usage patterns rapidly become a primary concern for such contemporary graph processing systems. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs that are generated by human activity. In this paper, we propose three space-efficient adjacency list representations that can be applied to any distributed graph processing system. Our suggested compact representations reduce respective memory requirements for accommodating the graph elements up to 5 times if compared with state-of-the-art methods. At the same time, our memory-optimized methods retain the efficiency of uncompressed structures and enable the execution of algorithms for large scale graphs in settings where contemporary alternative structures fail due to memory errors. Last but not least, we propose a tree-based space-efficient out-edge representation that favors mutations as well.

Keywords: Graph compression, Pregel, distributed computing.


Bib

                                            
Panagiotis Liakos, Katia Papakonstantinopoulou and Michael Sioutis. Pushing the Envelope in Graph Compression. In 23rd ACM International Conference on Information and Knowledge Management (CIKM), Shanghai, China, November 2014.

Pdf Presentation

Abstract

We improve the state-of-the-art method for the compression of web and other similar graphs by introducing an elegant technique which further exploits the clustering properties observed in these graphs. The analysis and experimental evaluation of our method shows that it outperforms the cur- rently best method of Boldi et al. by achieving a better compression ratio and retrieval time. Our method exhibits vast improvements on certain families of graphs, such as so- cial networks, by taking advantage of their compressibility characteristics, and ensures that the compression ratio will not worsen for any graph, since it easily falls back to the state-of-the-art method.

Keywords: Graph compression, compact graph representation, social network graphs, graph clustering.


Bib

@inproceedings{DBLP:conf/cikm/LiakosPS14,
  author    = {Panagiotis Liakos and
               Katia Papakonstantinopoulou and
               Michael Sioutis},
  title     = {Pushing the Envelope in Graph Compression},
  booktitle = {Proceedings of the 23rd {ACM} International Conference on Conference
               on Information and Knowledge Management, {CIKM} 2014, Shanghai, China,
               November 3-7, 2014},
  pages     = {1549--1558},
  year      = {2014},
  crossref  = {DBLP:conf/cikm/2014},
  url       = {http://doi.acm.org/10.1145/2661829.2662053},
  doi       = {10.1145/2661829.2662053},
  timestamp = {Fri, 07 Nov 2014 12:38:01 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/cikm/LiakosPS14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@proceedings{DBLP:conf/cikm/2014,
  editor    = {Jianzhong Li and
               Xiaoyang Sean Wang and
               Minos N. Garofalakis and
               Ian Soboroff and
               Torsten Suel and
               Min Wang},
  title     = {Proceedings of the 23rd {ACM} International Conference on Conference
               on Information and Knowledge Management, {CIKM} 2014, Shanghai, China,
               November 3-7, 2014},
  publisher = {{ACM}},
  year      = {2014},
  url       = {http://dl.acm.org/citation.cfm?id=2661829},
  isbn      = {978-1-4503-2598-1},
  timestamp = {Fri, 07 Nov 2014 11:13:50 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/cikm/2014},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}
Panagiotis Liakos, Katia Papakonstantinopoulou and Michael Sioutis. On the Effect of Locality in Compressing Social Networks. In Advances in Information Retrieval - 36th European Conference on IR Research (ECIR), pages 650--655, Amsterdam, The Netherlands, April 2014.

Pdf Poster

Abstract

We improve the state-of-the-art method for graph compression by exploiting the locality of reference observed in social network graphs. We take advantage of certain dense parts of those graphs, which enable us to further reduce the overall space requirements. The analysis and experimental evaluation of our method confirms our observations, as our results present improvements over a wide range of social network graphs.

Keywords: .


Bib

@inproceedings{DBLP:conf/ecir/LiakosPS14,
  author    = {Panagiotis Liakos and
               Katia Papakonstantinopoulou and
               Michael Sioutis},
  title     = {On the Effect of Locality in Compressing Social Networks},
  booktitle = {Advances in Information Retrieval - 36th European Conference on {IR}
               Research, {ECIR} 2014, Amsterdam, The Netherlands, April 13-16, 2014.
               Proceedings},
  pages     = {650--655},
  year      = {2014},
  crossref  = {DBLP:conf/ecir/2014},
  url       = {http://dx.doi.org/10.1007/978-3-319-06028-6_71},
  doi       = {10.1007/978-3-319-06028-6_71},
  timestamp = {Tue, 25 Mar 2014 08:50:13 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ecir/LiakosPS14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@proceedings{DBLP:conf/ecir/2014,
  editor    = {Maarten de Rijke and
               Tom Kenter and
               Arjen P. de Vries and
               ChengXiang Zhai and
               Franciska de Jong and
               Kira Radinsky and
               Katja Hofmann},
  title     = {Advances in Information Retrieval - 36th European Conference on {IR}
               Research, {ECIR} 2014, Amsterdam, The Netherlands, April 13-16, 2014.
               Proceedings},
  series    = {Lecture Notes in Computer Science},
  volume    = {8416},
  publisher = {Springer},
  year      = {2014},
  url       = {http://dx.doi.org/10.1007/978-3-319-06028-6},
  doi       = {10.1007/978-3-319-06028-6},
  isbn      = {978-3-319-06027-9},
  timestamp = {Tue, 25 Mar 2014 08:50:13 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ecir/2014},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}
 

Technical Reports

Panagiotis Liakos, Katia Papakonstantinopoulou and Michael Sioutis. A Simple Algorithm for Compressing Web-like Graphs Efficiently. Technical report, University of Athens, Greece, August 2013.

Pdf

Abstract

We introduce an efficient compression algorithm for web-like graphs that exploits the graph's structure to achieve better compression rate. In particular, we make use of the locality of reference in the graph, the node similarity and the power law distribution of its nodes' degrees, three properties usually observed in large sparse graphs that model networks created by human activity. Furthermore, our approach focuses on navigating through both the incoming and outgoing edges of each node in linear time. First experimental evaluations of the proposed algorithm indicate promising results.

Keywords: Graph compression, web graphs, social graphs, citation graphs, locality of reference.


Bib

@techreport{SiVaC,
  month = {August},
  author = {Panagiotis Liakos and Katia Papakonstantinopoulou and Michael Sioutis},
  title = {{A Simple Algorithm for Compressing Web-like Graphs Efficiently}},
  type = {Technical Report},
  year = {2013},
  institution = {University of Athens}
}
 
Panagiotis Liakos, Katia Papakonstantinopoulou and Michael Sioutis. SiVaC*: An Efficient Graph Compression Algorithm. Technical report, University of Athens, Greece, February 2013. Poster presented at WSDM '13 (1st prize).

Pdf Poster

Abstract

This paper introduces a new efficient graph compression algorithm for large-scale graphs that exploits the graph's structure to achieve better compression rate. In particular, we make use of the locality of reference in the graph and the power law distribution of its nodes’ degrees, two properties usually observed in large sparse graphs that model networks created by human activity. Furthermore, our approach focuses on navigating through both the incoming and outgoing edges of each node in linear time. First experimental evaluations of the proposed algorithm indicate promising results.

Keywords: Graph compression, web graphs, social graphs, citation graphs, locality of reference.


Bib

@techreport{SiVaC,
  month = {February},
  author = {Panagiotis Liakos and Katia Papakonstantinopoulou and Michael Sioutis},
  title = {{SiVaC*: An Efficient Graph Compression Algorithm}},
  type = {Technical Report},
  year = {2013},
  institution = {University of Athens}
}