network structure --- k-cliques vs p-cliques

Question

In network structure, what is the difference between k-cliques and p-cliques, can anyone give a brief explaination with examples? Thanks in advanced!

============================
EDIT: I found an online ppt while I am googling, please take a look on p.37 and p.39, can you comment on them?

Answer 1

Curiously, in the linked document, neither $n$-cliques nor $p$-cliques mean what mathematicians would consider to be their definitions.

Mathematical definition: An $n$-clique is a complete subgraph on $n$ vertices (Wikipedia ref.). [And a $p$-clique is an $n$-clique with $n$ replaced by $p$.]

The linked document instead uses the definitions:

An $n$-clique, where $n$ is a positive integer, is a collection $C$ of vertices in which any two vertices $u,v \in C$ have distance $\leq n$.

A $p$-clique, where $p$ is a real number between $0$ and $1$, is a collection $C$ of vertices in which any vertex has $\geq p |C|$ neighbors in $C$.

Essentially, the definition is used to identifying clique-like ways of finding dense clusters in networks.

Personally, I would avoid both of these definitions, since both $n$-cliques and $p$-cliques (according to these definitions) might not be cliques.