Network Analysis: Community detection
Abstract
We examine the problem of uncovering communities in complex networks whose elements and their respective associations manifest as streams of data. Community detection is applied in emerging computational environments and concerns critical applications in diverse areas. Despite the already expended related research efforts, the task of revealing the community structure of massive and rapidly-evolving networks remains very challenging. There is an emerging need for online approaches that ingest graph data as a stream. We propose a streaming-graph community-detection algorithm that expands seed-sets of nodes to communities. We consider an online setting and process a stream of edges while aiming to form communities using partial knowledge of the graph. We maintain very limited information regarding the nodes of the graph and the communities we seek, so that we effectively process large scale networks. In addition, we develop a technique that increases the accuracy of our algorithm considerably and propose a new clustering algorithm that allows for automatically deriving the size of the communities sought. Our experimental evaluation using ground-truth communities for a wide range of large real-word and synthetic networks shows that our approach achieves accuracy comparable or even better to the state-of-the-art non-streaming community detection algorithms. More importantly, we attain significant improvements in both execution time and memory requirements.
Index Terms—Local Community Detection, Graph Streams, Seed-set Expansion, Social Networks.
Bib
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 301--310, 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: Graph streams, community detection, cloud.
Bib
@inproceedings{DBLP:conf/IEEEcloud/LiakosPND19,
author = {Panagiotis Liakos and
Katia Papakonstantinopoulou and
Alexandros Ntoulas and
Alex Delis},
title = {DiCeS: Detecting Communities in Network Streams over the Cloud},
booktitle = {12th {IEEE} International Conference on Cloud Computing, {CLOUD} 2019,
Milan, Italy, July 8-13, 2019},
pages = {301--310},
year = {2019},
crossref = {DBLP:conf/IEEEcloud/2019},
url = {https://doi.org/10.1109/CLOUD.2019.00058},
doi = {10.1109/CLOUD.2019.00058},
timestamp = {Wed, 16 Oct 2019 14:14:54 +0200},
biburl = {https://dblp.org/rec/bib/conf/IEEEcloud/LiakosPND19},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/IEEEcloud/2019,
editor = {Elisa Bertino and
Carl K. Chang and
Peter Chen and
Ernesto Damiani and
Michael Goul and
Katsunori Oyama},
title = {12th {IEEE} International Conference on Cloud Computing, {CLOUD} 2019,
Milan, Italy, July 8-13, 2019},
publisher = {{IEEE}},
year = {2019},
url = {https://ieeexplore.ieee.org/xpl/conhome/8798376/proceeding},
isbn = {978-1-7281-2705-7},
timestamp = {Wed, 16 Oct 2019 14:14:54 +0200},
biburl = {https://dblp.org/rec/bib/conf/IEEEcloud/2019},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
Modeling and analyzing user (selfish) behavior in routing and social networks
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}
}
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}
}
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
Abstract
For various purposes and, in particular, in the context of data compression, a graph can be examined at three levels. Its structure can be described as the unlabeled version of the graph; then the labeling of its structure can be added; and finally, given then structure and labeling, the contents of the labels can be described. Determining the amount of information present at each level and quantifying the degree of dependence between them, requires the study of symmetry, graph automorphism, entropy, and graph compressibility. In this paper, we focus on a class of small-world graphs. These are geometric random graphs where vertices are first connected to their nearest neighbors on a circle and then pairs of non-neighbors are connected according to a distance-dependent probability distribution. We establish the degree distribution of this model, and use it to prove the model's asymmetry in an appropriate range of parameters. Then we derive the relevant entropy and structural entropy of these random graphs, in connection with graph compression.
Keywords: Entropy, information, lossless compression, random graph, random network, small-world graph, graphical structure, symmetry.
Bib
@misc{kontoyiannis2020compression,
title={Compression and Symmetry of Small-World Graphs and Structures},
author={Ioannis Kontoyiannis and Yi Heng Lim and Katia Papakonstantinopoulou and Wojtek Szpankowski},
year={2020},
eprint={2007.15981},
archivePrefix={arXiv},
primaryClass={cs.IT}
}
Pdf Presentation
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}
}
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}
}
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 social 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}
}
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
). The source code, written in Python, can be found here. More details to be added soon.
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}
}
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}
}