  Steganography aims to conceal the very fact that the communication takes
place, by embedding a message into a digit object such as image without
introducing noticeable artifacts. A number of steganographic systems have been
developed in past years, most of which, however, are confined to the laboratory
conditions where the real-world use of steganography are rarely concerned. In
this paper, we introduce an alternative perspective to steganography. A
graph-theoretic model to steganography on social networks is presented to
analyze real-world steganographic scenarios. In the graph, steganographic
participants are corresponding to the vertices with meaningless unique
identifiers. Each edge allows the two vertices to communicate with each other
by any steganographic algorithm. Meanwhile, the edges are associated with
weights to quantize the corresponding communication risk (or say cost). The
optimization task is to minimize the overall risk, which is modeled as additive
over the social network. We analyze different scenarios on a social network,
and provide the suited solutions to the corresponding optimization tasks. We
prove that a multiplicative probabilistic graph is equivalent to an additive
weighted graph. From the viewpoint of an attacker, he may hope to detect
suspicious communication channels, the data encoder(s) and the data decoder(s).
We present limited detection analysis to steganographic communication on a
network.
