On Hidden Groups in Communication Networks Jeffery Baumes Mark Goldberg Malik Magdon-Ismail William A. Wallace We describe models and efficient algorithms for detecting groups (communities) func- tioning in communication networks which use, intentionally or not, the surrounding background communications to disguise their existence. We call such groups hidden groups. To detect hidden groups we exploit the non-random nature of their communi- cations as contrasted with the general background communications. We assume that the main goal of the communications of a hidden group in the network is planning and coordination of their future activity, which by the nature of planning has to involve all, or most members of the group. The implication of this basic assumption is that the com- munication subgraph induced by the hidden group members is connected. We describe efficient algorithms that, under certain conditions, can detect connected subgraphs that remain connected over time. Our results reveal the properties of the background network activity and hidden group communication dynamics that make detection of the hidden group easy, as well as those that make it difficult. We differentiate between two types of hidden groups: in a trusting (or non-secretive) hidden group, members are willing to communicate messages to other members via non-hidden group members; in a non-trusting (or secretive) hidden group, all information that must be passed among hidden group members cannot be passed via non-hidden group members. We find that if the background communications are dense or more structured, then the hidden group is harder to detect. Surprisingly, we also find that when the hidden group is non-trusting (secretive), it is easier to detect. We also relax our definition of a hidden group to include those groups which persist in any subinterval of communication cycles, and present efficient algorithms and data-types for detecting and querying these groups. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-05-15
On Hidden Groups in Communication Networks
Jeffery Baumes
Mark Goldberg
Malik Magdon-Ismail
William A. Wallace
We describe models and efficient algorithms for detecting groups (communities) func- tioning in communication networks which use, intentionally or not, the surrounding background communications to disguise their existence. We call such groups hidden groups. To detect hidden groups we exploit the non-random nature of their communi- cations as contrasted with the general background communications. We assume that the main goal of the communications of a hidden group in the network is planning and coordination of their future activity, which by the nature of planning has to involve all, or most members of the group. The implication of this basic assumption is that the com- munication subgraph induced by the hidden group members is connected. We describe efficient algorithms that, under certain conditions, can detect connected subgraphs that remain connected over time. Our results reveal the properties of the background network activity and hidden group communication dynamics that make detection of the hidden group easy, as well as those that make it difficult. We differentiate between two types of hidden groups: in a trusting (or non-secretive) hidden group, members are willing to communicate messages to other members via non-hidden group members; in a non-trusting (or secretive) hidden group, all information that must be passed among hidden group members cannot be passed via non-hidden group members. We find that if the background communications are dense or more structured, then the hidden group is harder to detect. Surprisingly, we also find that when the hidden group is non-trusting (secretive), it is easier to detect. We also relax our definition of a hidden group to include those groups which persist in any subinterval of communication cycles, and present efficient algorithms and data-types for detecting and querying these groups.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-05-15