Mobile devices have become essential tools for many human actions—including, evidently, criminal and terrorist activities. Despite the secrecy surrounding the intelligence field, it is well known (as leaked recently by ex-NSA contractor Edward Snowden) that various intelligence agencies and law enforcement authorities make extensive use of monitoring communication channels as part of their daily operations and consider such monitoring as a valuable source of intelligence [36]. Data mining tools can be used to analyze billions of communication records to filter out noise and extract objects (following previous publications, hereinafter we will use the terms “object,” “user” and sometimes “device” interchangeably) that will subsequently be investigated in a more detailed and accurate manner [35]. Such large-scale information monitoring poses great challenges regarding the data collection technology used, privacy issues and the methods used to analyze the collected data. For example, it is essential to present the relevant information (such as users’ behavioral patterns) to domain experts who are not necessarily data scientists in a clear and intuitive way (graphically if possible) while maintaining a low computational complexity that allows scalability. The issue of privacy is of vital importance in such large-scale monitoring efforts. Users privacy has garnered wide public concern following the exposure of metadatamonitoring programs operated by US defense agencies such as the NSA as part of their increasing endeavors to fight terrorism after the 9/11 attacks [22,36]. Because we rely on metadata in our analysis, let us clearly state that there is no doubt that metadata contains extremely sensitive information and in many cases does not provide the required level of privacy, as has been shown in many studies (e.g., [13,24]). In fact, De Montjoye et al. [13] showed that a few spatiotemporal points of data are sufficient to uniquely iden tify 90% of individuals in a credit card behavioral study. Moreover, they showed that even data sets that convey only coarse information at any or all of the dimensions provide little anonymity. Note, however, that many of these studies addressed settings in which private experimental data are to be shared publicly (e.g., see [7,8]). The setting of this study is somewhat different because it considers a situation in which cellular providers or governmental agencies will use only metadata for the initial screening, although they are often authorized to access granular and private user communication content. Thus, a practical implication of this study is not whether to expose or publish private data but whether to try to provide some hierarchical layers of exposure in which metadata is used as a first alternative to a procedure that fully exposes user content. Moreover, although metadata provides less anonymity than anticipated, in many cases it guarantees a higher level of privacy than full content exposure. For example, Mayer et al. [24] specifically addressed privacy protection against government surveillance by comparing the exposure of the full content of communications to the exposure of only the metadata of those communications. The authors specifically discussed the US National Security Agency, which collects telephone metadata nationwide, and investigated the privacy properties of telephone metadata to assess the impact of monitoring policies that distinguish between content and metadata. Although the authors found that telephone metadata can be used to re-identify users as well as to reveal highly sensitive traits, their numerical studies showed that when using the metadata only a portion (although sometimes a significant one) of the telephone numbers could be re-identified.