The page is recovered from our old website (Internet Archive snapshot). Some of the links may be broken as what they pointed to no longer exist.
People
- Faculty: Athina Markopoulou (EECS), Carter T. Butts (Sociology).
- Postdocs: Minas Gjoka, Omer Nebil Yaveroglu
- PhD Students: Blerim Cici, Balint Tillman
- Collaborators: Natasa Przulj, Imperial College, London, UK.
- Past visitors: Kai Sun, Imperial College, London, UK; Luca Baldesi, University of Trento, Italy
- Past collaborators: Maciej Kurant
- Past students: Yan Wang (MSc)
Funding
This work was supported by the following grants:
- NSF Award 1526736, ” III: Small: Network Sampling and Construction Methods for Inference and Anonymization”
- NSF Award 1028394, “CDI-Type II: Local Topology and Function of Computer, Social, & Biological Networks”
- AFOSR MURI: “Information Dynamics as Foundation for Network Management”. AFOSR MURI prime award FA9550-09-0643 (subcontract to UCI from Princeton). 9/1/2009-8/31/2014.
- Docomo USA Labs contract: “OSNs from an Operator’s Perspective”.
Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsors.
Presentations
- May 2015: Athina’s HSSoE distinguished lecture on Measurement and Analysis of Social and Mobile Networks.
- March 2015: Athina’s overview talk on 2K+ construction, at the DataScience event at UCI
- 10/27/2014: Minas gives a talk at CSE Colloquium at UC Riverside.
- 2/16/2012: Athina gives a talk at CSSI Seminar Series at UMASS.
- Nov. 2012: Maciej gives a presentation on Sampling Massive Online Graphs: Challenges, Techniques, and Applications to Facebook at KTH, University of Helsinki and ETHZ
- 9/23/2011: Athina gives a seminar (overview of our work on Sampling Online Social Networks) at the Advanced Networks Colloqium at the University of Maryland, College Park.
- Earlier versions of this talk were presented at the at NNMC, Madison, WI, in May 2011; IMBS Workshop at UC Irvine, in Jan. 2011; and at the UCLA Colloqium in April 2011.
- Workshop on Exponential Random Graphs and the ERGM in statnet, by Carter Butts, Sept. 21st, 2011.
- Here is a poster presented at the CalIT2 anniversary on our ongoing work on Mobile Online Social Networks.
Publications
- Spectral Graph Forge: Graph Generation Targeting Modularity
[ bibtex , software, arxiv version ]
Luca Baldesi, Athina Markopoulou, Carter T. Butts
- Estimating Subgraph Frequencies with or without Attributes from Egocentrically Sampled Data
[ pdf, bibtex , slides, software, datasets ]
Minas Gjoka, Emily Smith, Carter T. Butts
- On the Decomposition of Cell Phone Activity Patterns and their Connection with Urban Ecology
[ pdf, bibtex , slides, software, datasets ]
Blerim Cici, Minas Gjoka, Athina Markopoulou, Carter T. Butts
ACM Mobihoc ’15.
- Construction of Simple Graphs with a Target Joint Degree Matrix and Beyond
[ pdf, bibtex , slides, software ]
Minas Gjoka, Balint Tillman, Athina Markopoulou
To appear in IEEE INFOCOM ’15.
- Assessing the Potential of Ride-Sharing Using Mobile and Social Data – A Tale of Four Cities
[ pdf, bibtex , slides, software ]
Blerim Cici, Athina Markopoulou, Enrique Frias-Martinez, Nikolaos Laoutaris
UbiComp ’15.
- Efficient Construction of 2K+ Graphs
[ pdf, bibtex , slides, abstract, software ]
Minas Gjoka, Balint Tillman, Athina Markopoulou, Rasmus Pagh
NetSci 2014 Posters.
- Estimating Clique Composition and Size Distributions from Sampled Network Data
[ pdf, bibtex , slides, software ]
Minas Gjoka, Emily Smith, Carter T. Butts
To appear in IEEE INFOCOM, NetSciCom Workshop ’14 and on arXiv:cs.SI:1308.3297, Aug. 2013.
- 2.5K-Graphs: from Sampling to Generation
[ pdf, bibtex , slides, software ]
Minas Gjoka, Maciej Kurant, Athina Markopoulou
To appear in IEEE INFOCOM ’13 and on arXiv:cs.SI:1208.3667.
- Quantifying the Potential of Ride-Sharing using Call Description Records
[ pdf, bibtex , slides, software ]
Blerim Cici, Athina Markopoulou, Enrique Frias-Martinez, Nikolaos Laoutaris
HotMobile ’13.
- Coarse-Grained Topology Estimation via Graph Sampling
[ pdf, bibtex , slides, report, dataset, software ]
Maciej Kurant,Minas Gjoka, Yan Wang, Zack W. Almquist,Carter T. Butts, , Athina Markopoulou
SIGCOMM Workshop on Online Social Networks (WOSN) ’12, and available at arXiv:cs.SI:1105.5488
- Multigraph Sampling of Online Social Networks
[ pdf , bibtex , slides, dataset ]
Minas Gjoka, Carter T. Butts, Maciej Kurant, Athina Markopoulou
JSAC special issue on Measurement of Internet Topologies, Vol.29, No. 9, Oct. 2011.
- Practical Recommendations on Crawling Online Social Networks
[ pdf, bibtex, slides, dataset1, dataset2, software ]
Minas Gjoka, Maciej Kurant, Carter T. Butts, Athina Markopoulou
JSAC special issue on Measurement of Internet Topologies, Vol.29, No. 9, Oct. 2011.
- Towards Unbiased BFS Sampling
[ pdf ]
Maciej Kurant, Athina Markopoulou, Patrick Thiran
JSAC special issue on Measurement of Internet Topologies, Vol.29, No. 9, Oct. 2011. - Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks
[ pdf, bibtex , slides, dataset ]
Maciej Kurant, Minas Gjoka, Carter T. Butts, Athina Markopoulou,
ACM SIGMETRICS 2011.
- On the Bias of Breadth First Search (BFS) and of Other Graph Sampling Techniques
[ pdf, bibtex, slides, report ]
Maciej Kurant, Athina Markopoulou, Patrick Thiran
International Teletraffic Congress (ITC 22) ’10, Amsterdam, Sept 2010
- Walking in Facebook: A Case Study of Unbiased Sampling of OSN
[ pdf, bibtex, slides, dataset1, dataset2, software ]
Minas Gjoka, Maciej Kurant, Carter T. Butts, Athina Markopoulou
IEEE INFOCOM ’10, San Diego, March 2010
- Poking Facebook: Characterization of OSN Applications
[ pdf, bibtex, slides, dataset, software ]
Minas Gjoka,Michael Sirivianos, Athina Markopoulou, Xiaowei Yang
ACM SIGCOMM Workshop on Online Social Networks (WOSN) ’08,Seattle, August 2008
Released Datasets
Please see: Online Social Networks: Dataset
- Facebook Egonet Samples
- Last.fm Multigraph
- Facebook Geosocialmap
- Facebook Social Graph – MHRW & UNI
- Facebook Social Graph – Breadth First Search
- Facebook Applications
- Facebook Weighted Random Walks
Released Software
This section is recovered from here.
Software released by Online Social Networks project
- 2K Simple: We release a reference implementation (in both Python and C++) of the graph construction algorithm 2K_Simple that was presented in our paper Construction of Simple Graphs with a Target Joint Degree Matrix and Beyond. 2K_Simple receives as input a Joint Degree Matrix (JDM) and provably constructs a simple graph with the given JDM in running time O(|E|*d_max) where |E| is number of edges and d_max is the maximum degree as defined by the given JDM. Finally, we have integrated the 2K_Simple algorithm in the NetworkX Python package (version >=2.0).
- Clique Estimation: two Python scripts that demonstrate the estimators described in our paper Estimating Clique Composition and Size Distributions from Sampled Network Data. The first script implements two types of unbiased estimators of clique size distributions, one of which exploits labeling of sampled nodes neighbors and one of which does not require this information. Additionally, it supports the compositions of cliques by node attributes (only supports binary node attributes, such as gender). The second script demonstrates how to prepare the data for input to the first script. More specifically, it receives as input a known graph, sampling parameters (sampling method, sampling size, replacement type), and clique distribution preferences (labeling, attributes). It then appropriately samples egonets from the given graph and calculates the maximal clique distribution for each sampled egonet.
- 2.5K-Graphs: two software packages to demonstrate the algorithms and estimators described in our paper 2.5K-Graphs: from Sampling to Generation. The first package receives as input a random walk graph sample and estimates the degree-dependent clustering coefficient distribution and network average clustering coefficient. The second package implements all the algorithms and estimators within classes “Estimation” and “Generation”. It receives as an input a fully known graph and then simulates a random walk graph sample of given size. The class “Estimation” provides functions that estimate the degree-dependent clustering coefficient (CCK) and joint degree distribution (JDD). The class “Generation” provides functions that generate a 2.5K graph given specific CCK and JDD distributions.
- Geosocialmap: a web-based tool that visualizes geo-social data. More information can be found in our paper Coarse-Grained Topology Estimation via Graph Sampling and the M.Sc. thesis GeoSocialMap Visualization
- Graph sampling: A set of functions to sample nodes of a graph with replacements (Simple Random Walk, Weighted Random Walk, Metropolis Hastings Random Walk, Uniform Independent Sampling, Weighted Independent Sampling) and corresponding estimators.
- Facebook Applications: protype crawlers of the Facebook user profiles in 2008 and user coverage simulator. More information can be found in our paper Poking Facebook: Characterization of OSN Applications