ComputationalModelsand Algorithmsof Hidden Groups InCommunication Network

After the tragic events of Sep.11, 2001, people want to find a tool, which can detect groups (communities) functioning in communication networks which attempts to hide their functionality– hidden groups. Except for terrorists, we can also regard thieves as hidden groups. We discussed algorithms to discover hidden groups in this article, and proved the algorithms by some tests. So the result of this subject can be widely used where hidden group can hide. So it can contribute to safety of our country and stability of our society.We sorted hidden groups into Internally-Connected hidden groups and Externally-Connected hidden groups. We use different methods to deal with different type of hidden groups. We use Hidden Markov Model to simulate Externally-Connected hidden groups. We assume the structure of the society is a Markov chain, and communications between nodes are independent, and communication graphs at some time are only determined by the structure of the society at this time, so we build the communication model of the society. We generate communication time series according the model, and then we can deduce whether there is a hidden group according results computed by our algorisms, and get the structure of the society. If there are 20 time steps of communication data, we can conclude whether there is a hidden group with the probability of 80%, and get the structure of the society. We use Random Graph Model to simulate Internally-Connected hidden groups. The communication probability between any two nodes in the society is p in the Random Graph Model. If every two nodes in a group are connected at every time, we can deduce that these nodes are in a hidden group. We also discuss the size of hidden groups. If the communication probability between nodes is less than 1/n (n is the number of nodes in the society), there is not a hidden group in the society. If the communication probability between nodes is more than , the size of hidden groups almost is n. We can easily find out hidden groups at this time, and also can find out the numbers of hidden groups. logn /n...