Pattern detection (Structural) Within Large Complex Network Graphs
Research Topic Description, including Problem Statement:
Social networks, Internet of Things (IoT), software development and vulnerability assessments are examples of areas that can be modelled and understood using graph theory and complex network analysis. Graph theory allows a variety of scenarios across a range of areas to be represented as networks and analyzed to identify structures and behaviors.
The structure of the network is key to its function and the discovery of repeating structural patterns across a single large complex network is of particular interest. Currently, pattern discovery within a scenario of interest can only be undertaken manually. This is very time consuming due to the size of both the network and the patterns. The scale and breadth of network structures are increasing rapidly, whilst some are expanding into temporal and dynamic datasets (e.g. IoT). This impacts the viability of manual pattern detection.
To date, limited research has been undertaken to identify ways of overcoming this problem. There are no known algorithms available to discover large (~50-100 nodes) patterns within a single large complex network, although progress is being made through the use of novel approaches e.g. motif detection and graph neural networks.
Although open source complex network datasets are available, none have been found to contain sufficient repeating patterns for training and testing or exploration. Open source datasets of complex networks that are available and potentially adaptable, include, but are not limited to:
- https://www.cnn.group.cam.ac.uk/Resources
- https://github.com/gephi/gephi/wiki/Datasets
- http://www.ee.cityu.edu.hk/~gchen/ComplexNetworks/SoftwareDatabases.htm
Example Approaches:
A scalable method for discovery of large repeating patterns within a single large complex network is required. The key requirement for this project is to research, identify and develop algorithms or produce innovative solutions that could identify repeating patterns across a single large complex network.
Current focus of research is the discovery of exact matching large patterns (~50-100 nodes) within a static complex network. Future work may include extending the research to discover patterns within a temporal and dynamic complex network dataset. Proposals that consider a methodology which can be extended are sought, as there is potential to extend this work for a 3rd year.
Research proposals could include:
- Research into available algorithms and assessment of suitability for adaption or extension. Proposed methods will be assessed against:
- Ability to cope with hierarchical pattern discovery.
- Potential for node categories to be considered.
- Discovery of exact matching patterns.
- Discovery of similar patterns.
- Development of one or more methods for assessing against open source data.
- Improvement of method dependent on test results.
- Potential to adapt deliverable for pattern discovery on a temporal or dynamic dataset.
Technical partnering will be provided. Throughout the project, regular delivery of working scripts is required to enable in-house testing on data. Where possible following internal testing, feedback on performance will be provided.
Relevance to the Intelligence Community:
Pattern discovery using graph theory has several identified use cases across the Intelligence Community (IC) including:
- Increase efficiency of software development through identification of repeating blocks.
- Improve assurance of software development by increase in tools available for software analysis.
- Increase efficiency of design assurance for electronic circuitry.
- Citation patterns in scientific literature to inform future threat areas.
- Identification of repeating, interlinked events across a sensor network (“Internet of Things”)
- Exploration of neural networks for assurance.
This work is also considered a stepping-stone to enable improved analysis of applications outlined above where the data extends to temporal or dynamic datasets. This research would enable:
- Identification of repeating events, which propagate across multiple timestamps and nodes within a network.
- Identification of distributed impacts of events across a connected network – events may appear unconnected to a human but the aspiration is that this algorithm could detect a repeated connection.
This ability would be far reaching, contributing to a large number of capabilities across the IC. The specific project contributes to one of the key capabilities within the counterterrorism and security.
Key Words:
Large Complex Networks, Scalable, Pattern Detection, Graph Theory, Internet of Things, IoT, Structural Networks
Postdoc Eligibility
- U.S. citizens only
- Ph.D. in a relevant field must be completed before beginning the appointment and within five years of the application deadline
- Proposal must be associated with an accredited U.S. university, college, or U.S. government laboratory
- Eligible candidates may only receive one award from the IC Postdoctoral Research Fellowship Program
Research Advisor Eligibility
- Must be an employee of an accredited U.S. university, college or U.S. government laboratory
- Are not required to be U.S. citizens
How to Apply
Create and release your Profile on Zintellect – Postdoctoral applicants must create an account and complete a profile in the on-line application system. Please note: your resume/CV may not exceed 2 pages.
Complete your application – Enter the rest of the information required for the IC Postdoc Program Research Opportunity. The application itself contains detailed instructions for each one of these components: availability, citizenship, transcripts, dissertation abstract, publication and presentation plan, and information about your Research Advisor co-applicant.
Additional information about the IC Postdoctoral Research Fellowship Program is available on the program website located at: https://orise.orau.gov/icpostdoc/index.html.
If you have questions, send an email to ICPostdoc@orau.org. Please include the reference code for this opportunity (ICPD-2020-37) in your email.