Network Analysis

Panagiotis Liakos, Katia Papakonstantinopoulou, Alex Delis and Alexandros Ntoulas. DICES: Detecting Communities in Network Streams Over the Cloud. In Proceedings of the IEEE International Conference on Cloud Computing (CLOUD 2019), pages TBA, Milan, Italy, July 2019.

Pdf Presentation

Abstract

We consider a network whose elements and their respective relations manifest through streams and study the problem of uncovering communities starting from a few similar nodes. Community detection is a fundamental problem in the study of networks and has recently garnered significant interest due to the prevalence of online social networks. The focus of research efforts has lately shifted to streaming approaches, to handle the unprecedented volume of real-world networks. We propose here a distributed streaming community detection approach we call DICES and implement the respective cloud application. Our novel approach balances the incoming load to a cluster of worker nodes and allows for adjusting our processing capacity in an elastic manner. Additionally, we offer flexibility with regards to i) updating the target communities, and ii) obtaining results on demand. Lastly, DICES is fault tolerant, as we ensure that failed worker nodes are restored and all edges of the network stream are processed. Our experimental results show that DICES processes the edges of real-world network streams at impressive rates. Moreover, our design allows for almost linear scaling. Thus, we can greatly outperform previous non-distributed approaches using just a few worker nodes. Finally, our experimental evaluation using ground-truth communities for a wide range of large real-word networks shows that our proposed approach achieves improved accuracy compared to earlier algorithms.

Keywords: TBA.


Bib

TBA
 

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. Realizing Memory-Optimized Distributed Graph Processing. In IEEE Transactions on Knowledge and Data Engineering (TKDE), Volume 30 (4), pages 743-756, April 2018.

Pdf

Abstract

A multitude of contemporary applications heavily involve graph data whose size appears to be ever–increasing. This trend shows no signs of subsiding and has caused the emergence of a number of distributed graph processing systems including Pregel, Apache Giraph and GraphX. However, the unprecedented scale now reached by real-world graphs hardens the task of graph processing due to excessive memory demands even for distributed environments. By and large, such contemporary graph processing systems employ ineffective in-memory representations of adjacency lists. Therefore, memory usage patterns emerge as a primary concern in distributed graph processing. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs generated by human activity. In this paper, we propose 1) three compressed adjacency list representations that can be applied to any distributed graph processing system, 2) a variable-byte encoded representation of out-edge weights for space-efficient support of weighted graphs, and 3) a tree-based compact out-edge representation that allows for efficient mutations on the graph elements. We experiment with publicly-available graphs whose size reaches two-billion edges and report our findings in terms of both space-efficiency and execution time. Our suggested compact representations do 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.

Keywords: Distributed graph processing, graph compression, Pregel.


Bib

@article{DBLP:journals/tkde/LiakosPD18,
  author    = {Panagiotis Liakos and
               Katia Papakonstantinopoulou and
               Alex Delis},
  title     = {Realizing Memory-Optimized Distributed Graph Processing},
  journal   = {{IEEE} Trans. Knowl. Data Eng.},
  volume    = {30},
  number    = {4},
  pages     = {743--756},
  year      = {2018},
  url       = {http://doi.ieeecomputersociety.org/10.1109/TKDE.2017.2779797},
  doi       = {10.1109/TKDE.2017.2779797},
  timestamp = {Wed, 14 Mar 2018 16:26:01 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/tkde/LiakosPD18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}                                            
A preliminary version of this work appeared in:

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

@inproceedings{DBLP:conf/cikm/LiakosPD16,
  author    = {Panagiotis Liakos and
               Katia Papakonstantinopoulou and
               Alex Delis},
  title     = {Memory-Optimized Distributed Graph Processing through Novel Compression
               Techniques},
  booktitle = {Proceedings of the 25th {ACM} International Conference on Information
               and Knowledge Management, {CIKM} 2016, Indianapolis, IN, USA, October
               24-28, 2016},
  pages     = {2317--2322},
  year      = {2016},
  crossref  = {DBLP:conf/cikm/2016},
  url       = {http://doi.acm.org/10.1145/2983323.2983687},
  doi       = {10.1145/2983323.2983687},
  timestamp = {Thu, 13 Jul 2017 17:21:47 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/cikm/LiakosPD16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/cikm/2016,
  editor    = {Snehasis Mukhopadhyay and
               ChengXiang Zhai and
               Elisa Bertino and
               Fabio Crestani and
               Javed Mostafa and
               Jie Tang and
               Luo Si and
               Xiaofang Zhou and
               Yi Chang and
               Yunyao Li and
               Parikshit Sondhi},
  title     = {Proceedings of the 25th {ACM} International Conference on Information
               and Knowledge Management, {CIKM} 2016, Indianapolis, IN, USA, October
               24-28, 2016},
  publisher = {{ACM}},
  year      = {2016},
  url       = {http://doi.acm.org/10.1145/2983323},
  doi       = {10.1145/2983323},
  isbn      = {978-1-4503-4073-1},
  timestamp = {Thu, 13 Jul 2017 17:21:47 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/cikm/2016},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}                                            
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}
}
 
Summer 2015
With Panagiotis Liakos we have improved the graph representations in popular graph processing systems. More details to be added soon.

Summer 2014
With Panagiotis Liakos and Mike Sioutis we have improved the state-of-the-art algorithm for compressing web and social network graphs.
The algorithm is proper for compressing graphs created by human activity (e.g., web/social network/citation graphs), or any other sparse graph exhibiting the locality of reference property.
Our approach is outlined in this presentation (presented at CIKM '14). The source code, written in Java, can be found here.

Spring 2013
With Panagiotis Liakos and Mike Sioutis we have developed a graph compression algorithm that allows efficient mining of the graph's elements.
The algorithm is proper for compressing graphs created by human activity (e.g., web/social network/citation graphs), or any other sparse graph exhibiting the locality of reference property.
Our approach is outlined in this poster (presented at WSDM '13 1st place in data challenge). The source code, written in Python, can be found here.

More details to be added soon.
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}
}