Title :
Computing Cross Associations for Attack Graphs and Other Applications
Author :
Heydari, M.H. ; Morales, L. ; Shields, C.O. ; Sudborough, I.H.
Author_Institution :
Dept. of Comput. Sci., James Madison Univ., Harrisonburg, VA
Abstract :
Applications in information security, data mining, e-commerce, information retrieval and network management require the analysis of large graphs in order to discover homogeneous groupings of rows and columns, called cross associations. We show that finding an optimal cross association is NP-complete. Furthermore, we give a heuristic algorithm with an O(n4) running time for finding good cross associations
Keywords :
computational complexity; graph theory; security of data; NP-complete problem; attack graphs; data mining; e-commerce; heuristic algorithm; information retrieval; information security; network management; optimal cross association finding; Application software; Bipartite graph; Business; Computer networks; Computer science; Data mining; Information analysis; Information retrieval; Information security; Information systems;
Conference_Titel :
System Sciences, 2007. HICSS 2007. 40th Annual Hawaii International Conference on
Conference_Location :
Waikoloa, HI
Electronic_ISBN :
1530-1605
DOI :
10.1109/HICSS.2007.141
