A Probabilistic Computational Model for Identifying Organizational Structures from Uncertain Activity Data

Volume Number:
Issue Number:
Starting page
Ending page
Publication Date:
Publication Date
1 June 2012
Xu Han, Feili Yu, Georgiy Levchuck, Krishna Pattipati, Fang Tu

paper Menu


The knowledge of the principles and goals under which an adversary organization operates is required to predict its future activities. To implement successful counter-actions, additional knowledge of the specifics of the organizational structures, such as command, communication, control, and information access networks, as well as responsibility distribution among members of the organization, is required. Our focus here is on identifying the mapping between hypothesized nodes of an adversary command organization (“model network”) and tracked individuals, resources and activities (“data network”). We formulate the organizational structure identification problem as one of associating the nodes of the noisy data network with the nodes of the model network. The problem of minimizing the negative log likelihood ratio with respect to the mapping versus null mapping (thereby capturing the possibility that no hypothesized model network is a good match) leads to a Quadratic Assignment Problem (QAP). We solve the QAP using what we call an iterative m-best soft assignment algorithm, combining Bertsekas’ auction algorithm and Murty’s m-best assignment algorithms in a novel way.

The experimental results show that our probabilistic model and the m-best soft assignment-based algorithm can accurately identify the different organizational structures and achieve correct node map-pings among organizational members under uncertainty. We also apply the m-best soft assignment algorithm to the general QAP and compare its performances to the hitherto best solutions.