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. […]
Suppose that balls, where is a constant, are thrown sequentially to bins, all of which are initially empty. Let be the number of empty bins after we have thrown balls. Clearly, . Let’s see how we can understand this sequence of random variables. When we move from step to we throw a ball. It either falls in an […]
The sphericity of a graph is the smallest dimension such that there exists a mapping such that if and only if . The following theorem is due to Frankl and Maehara and is a nice application of random projections. Here, . Theorem [Frankl-Maehara 1988]: Let be a graph with minimum adjacency eigenvalue where and suppose . […]
tsourakakis.com 