Abstract: The increasing interconnectivity of complex engineered system of systems (SoS) leads to difficulties ensuring systems architectures are of sufficient quality (availability, maintainability, reliability, etc.). Typically reductionist approaches are used during systems architecting which may fail to provide the desired insights into key relationships and behaviors. New approaches are therefore needed and this work shows how tools from complexity science can be applied. Data from a NATO Architecture Framework complex SoS architecture, based on a Search and Rescue Use Case, is modelled using graph theory. The analysis includes degree distribution, density, connected components and modularity. Such analysis supports architectural decision making such as dependency allocation, boundary identification, areas of focus and selection between architectures. It is shown how the analysis from complexity science can be used to analyze complex SoS architectures, to provide an alternative view, that explores relationships and structure in a non-reductionist, general approach when considering architecture decisions.