The Cut and Dominating Set Problem in A Steganographer Network
This work addresses steganography detection and control in social networks, but it is incremental as it applies existing graph theory problems to a new domain.
The paper tackles the problem of modeling steganographic communication as a network and analyzes two specific problems: a passive attack to disconnect suspicious vertices with minimal cost, and determining a set of sender vertices for message sharing, which are equivalent to the minimum cut and minimum-weight dominating set problems.
A steganographer network corresponds to a graphic structure that the involved vertices (or called nodes) denote social entities such as the data encoders and data decoders, and the associated edges represent any real communicable channels or other social links that could be utilized for steganography. Unlike traditional steganographic algorithms, a steganographer network models steganographic communication by an abstract way such that the concerned underlying characteristics of steganography are quantized as analyzable parameters in the network. In this paper, we will analyze two problems in a steganographer network. The first problem is a passive attack to a steganographer network where a network monitor has collected a list of suspicious vertices corresponding to the data encoders or decoders. The network monitor expects to break (disconnect) the steganographic communication down between the suspicious vertices while keeping the cost as low as possible. The second one relates to determining a set of vertices corresponding to the data encoders (senders) such that all vertices can share a message by neighbors. We point that, the two problems are equivalent to the minimum cut problem and the minimum-weight dominating set problem.