Social Networks are best represented as complex interconnected graphs. Graph theory analysis can hence be used for insight into various aspects of these complex social networks. Privacy of such networks lately has been challenged and a detailed analysis of such networks is required. This paper applies key graph theory concepts to analyze such social networks. Moreover, it also discusses applications and proposal of a novel algorithm to analyze and gather key information from terrorist social networks. Investigative Data Mining is used for this which is defined as when Social Network Analysis (SNA) is applied to Terrorist Networks to gather useful insights about the network..