Online Social Networks

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:

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

Publications

  • Estimating Subgraph Frequencies with or without Attributes from Egocentrically Sampled Data
    [ pdf, bibtex , slides, software, datasets ]
    Minas Gjoka, Emily Smith, Carter T. Butts

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