Category Big Data

Provably Fast Inference of Latent Features from Networks

Latent feature learning: where overlapping communities, correlation clustering, binary matrix factorization and extremal graph theory meet Motivation: Suppose we are given the following. Agents: Five agents, represented by . Binary vertex features. An agent can either be interested or not in each out of three news categories business, entertainment, sports.  Each interest is represented by a […]

Maintaining a random sample of edges on a dynamic graph

Suppose that we have a sample of edges, sampled uniformly at random from the edge set of a graph . Also, let . Now the graph changes, in particular, either a non-existing edge (if the graph is not complete) is inserted or an existing edge is deleted. Do we need to sample edges from scratch?More generally, […]

k-clique densest subgraph problem

Motivation: Suppose you are given a large “who-calls-whom” network. This is a network where each vertex represents a human and we have an (undirected) edge between two humans if and only if they exchanged a phone call. An important problem that comes up in anomaly detection is finding sets of vertices that “look like” cliques. […]