Optimisation of the scalable partitioning of complex network graphs for processing

Organization
Office of the Director of National Intelligence
Reference Code
ICPD-2019-19
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 in your email. 

Application Deadline
3/1/2019 6:00:00 PM Eastern Time Zone
Description

Research Topic Description, including Problem Statement:

  • Complex networks are widely used to represent a variety of scenarios: from social networks and terrorist cell structures to airline routing, as well as being used in image processing and biology. They can be used to represent any system and harness methods to identify control points, communities and key players. The structure of the network is key to its function. Often, the analysis of these networks is undertaken manually however the scale and breadth of these networks in all scenarios are vastly increasing and becoming more complex. This leads to very large networks which are too large for manual analysis and increasingly reaching limits on computational processing. The size of these networks is expected to continue to increase exponentially.
  • For several months, limited research has been undertaken to identify ways of overcoming this problem. There are a limited number of algorithms available to process such large datasets, and most require setting a pre-determined number of partitions.

Some algorithms found include:

  • Overview of algorithms:

https://pdfs.semanticscholar.org/7a84/d1bf4f4b24f178fec8b7c685fa1459d5829a.pdf

  • Graph partitioning based on spreading the load across a pre-defined number of computers:

https://link.springer.com/article/10.1007/s41019-017-0034-4

  • Partitioning based on structure of graph:

https://arxiv.org/pdf/1806.00907.pdf

  • Open source datasets of complex networks are available for use including:

https://github.com/gephi/gephi/wiki/Datasets

http://www.ee.cityu.edu.hk/~gchen/ComplexNetworks/SoftwareDatabases.htm

 

Example Approaches:

  • A scalable method for partitioning complex network graphs into an optimal number of parts is required. This could be approached by:
    • Research into available algorithms and assessment of suitability for implementation and/or adaption. Any methods should be considered against
      • Scalability
      • Consideration of preserving key network structure
      • Optimization of number of partitions.
    • Consideration of data flow techniques as emerging methods for understanding the underlying structure of networks.
    • Implementation of one or more methods for assessing against open source data
    • Updating of method dependent on test results.
    • Technical partnering will be provided.

 

Key Words:

Large complex networks; Scalable; Optimisation; Partition; Graph theory

Qualifications

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
Eligibility Requirements
  • Citizenship: U.S. Citizen Only
  • Degree: Doctoral Degree.
  • Discipline(s):
    • Communications and Graphics Design (6 )
    • Computer Sciences (17 )
    • Earth and Geosciences (23 )
    • Engineering (27 )
    • Environmental and Marine Sciences (13 )
    • Life Health and Medical Sciences (47 )
    • Mathematics and Statistics (11 )
    • Nanotechnology (1 )
    • Other Physical Sciences (12 )
    • Physics (16 )
    • Social and Behavioral Sciences (36 )