
## 1 Introduction

Covert nodes refer to persons who transmit the influence and affect the resulting collaborative activities among the persons in a social network, but do not appear in the surveillance logs which record the participants of the activities. The covert nodes are not observable directly. It aids us in discovering and approaching to the covert nodes to identify the suspicious surveillance logs where the covert nodes would appear if they became overt. I call this problem a node discovery problem for a social network.

Where do we encounter such a problem? Globally networked clandestine organizations such as terrorists, criminals, or drug smugglers are great threat to the civilized societies [Sageman (2004)]. Terrorism attacks cause great economic, social and environmental damage. Active non-routine responses to the attacks are necessary as well as the damage recovery management. The short-term target of the responses is the arrest of the perpetrators. The long-term target of the responses is identifying and dismantling the covert organizational foundation which raises, encourages, and helps the perpetrators. The threat will be mitigated and eliminated by discovering covert leaders and critical conspirators of the clandestine organizations. The difficulty of such discovery lies in the limited capability of surveillance. Information on the leaders and critical conspirators are missing because it is usually hidden by the organization intentionally.

Let me show an example in the 9/11 terrorist attack in 2001 [Krebs (2002)]. Mustafa A. Al-Hisawi, whose alternate name was Mustafa Al-Hawsawi, was alleged to be a wire-puller who had acted as a financial manager of Al Qaeda. He had attempted to help terrorists enter the United States, and provided the hijackers of the 4 aircrafts with financial support worth more than 300,000 dollars. Furthermore, Osama bin Laden is suspected to be a wire-puller behind Mustafa A. Al-Hisawi and the conspirators behind the hijackers. These persons were not recognized as wire-pullers at the time of the attack.

They were the nodes to discover from the information on the collaborative activities of the perpetrators and conspirators known at that moment.

In this paper, I present two methods to solve the node discovery problem. One is a heuristic method in
[Maeno (2009)], which demonstrates a simulation experiment of the node discovery problem for the social network of the 9/11 perpetrators. The other is a statistical inference method which I propose in this paper.

The method employs the maximal likelihood estimation and an anomaly detection technique. Section 3 defines the node discovery problem mathematically. Section 4 presents the two methods. Section 5 introduces the test dataset generated from computationally synthesized networks and a real clandestine organization.

Section 6 demonstrates the performance characteristics of the methods (precision, recall, and van Rijsbergen's F measure [Korfhuge (1997)]). Section 7 presents the issues and future perspectives as concluding remarks. Section 2 summarizes the related works.

## 2 Related Work

The social network analysis is a study of social structures made of nodes which are linked by one or more specific types of relationship. Examples of the relationship are influence transmission in communication or presence of trust in collaboration [Lavra˘c (2007)]. Network topological characteristics of clandestine terrorist organizations [Krebs (2002)] and criminal organizations [Klerks (2002)] are studied. Trade-off between staying secret and efficiently securing coordination and control is of particular interest [Morselli (2007)]. The impact of the network topology to the trade-off is analyzed
[Lindelauf (2009)].

Research interests have been moving from describing organizational structure to discovering dynamical phenomena on a social network. A link discovery predicts the existence of an unknown link between two nodes from the information on the known attributes of the nodes and the known links [Clauset (2008)]. It is one of the tasks of link mining [Getoor (2005)]. The link discovery techniques are combined with domainspecific heuristics. The collaboration between scientists can be predicted from the published co-authorship
[Liben-Nowell (2004)]. The friendship between people is inferred from the information available on their web pages [Adamic (2003)].

Markov random network is a model of the joint probability distribution of random variables. It is an undirected graphical model similar to a Bayesian network.

The Markov random network is used to learn the dependency between the links which shares a node. The Markov random network is one of the dependence graphs [Frank (1986)], which models the dependency between links. Extension to hierarchical models [Lazega (1999)],
multiple networks (treating different types of relationships) [Pattison (1999)], valued networks (with nodal attributes) [Robins (1999)], higher order dependency between the links which share no nodes [Pattison (2002)],
and 2-block chain graphs (associating one set of explanatory variables with the other set of outcome variables) [Robins (2001)] are studied. A family of such extensions and model elaborations is named the exponential random graph [Anderson (1999)]. In addition to the link discovery, the related research topics are the exploration of an unknown network structure [Newman (2007)], the discovery of a community structure [Palla (2005)], the inference of a network topology [Rabbat (2008)], the detection of an anomaly in a network [Silva (2009)], and the discovery of unknown nodes [Maeno (2007)], [Maeno (2009)]. Stochas-