Methods and systems for node and link identification

Inventors

Krause, Lee S.Schneider, James B.McQueary, Bruce R.Hagan, Craig T.Thornton, Sean K.LaMonica, Peter M.Anken, Craig S.Guestrin, Carlos

Assignees

Securboration IncUnited States Department of the Air Force

Publication Number

US-9372929-B2

Publication Date

2016-06-21

Expiration Date

2034-03-20

Interested in licensing this patent?

MTEC can help explore whether this patent might be available for licensing for your application.


Abstract

Methods and systems for node and link detection in social network analysis. Interactive noise reduction allows reduction of the data set under analysis to enable substantially real time detection of links and nodes.

Core Innovation

The invention provides methods and systems for node and link detection in social network analysis, employing interactive noise reduction to reduce the data set under analysis, enabling substantially real-time detection of links and nodes. It combines semantic processing, term recommendation, data acquisition, noise reduction, and link detection algorithms within a computing framework, including use of algorithms such as the Linear Sub-Modular Bandits Greedy algorithm (LSB) combined with multi-dimensional feature analysis.

The invention addresses the problem of analyzing massive, constantly changing social media data streams where manual analysis is impractical due to data size and noise. It provides automated methods to cull relevant information from noisy data and to identify implicit and explicit relationships (nodes and links) between users in social media data streams with minimal manual intervention.

The system includes interactive features allowing user feedback to iteratively refine noise reduction and identification of influential nodes and links substantially in real time, enabling fast updates as new data arrives. This process uses online learning algorithms and parallel computing frameworks such as GraphLab or GraphChi to handle large-scale data and improve performance over offline methods, permitting scalable and efficient social network analysis.

Claims Coverage

The patent includes three independent claims covering a method, a system, and a method for motif recognition in social network analysis. The claims focus on interactive term recommendation, noise reduction, and identification of influential nodes and links using user feedback and specific algorithms.

Interactive network analysis using search term recommendation and feedback

A method comprising receiving at least one search term, querying a recommendation engine to retrieve additional related terms, retrieving information related to these terms from a data store, providing this information, receiving user feedback on its relevance, and identifying influential nodes and links in the retrieved information using the feedback.

System for network analysis integrating recommendation engine, data store, and user feedback

A system including an interface to receive search terms and feedback, a recommendation engine connected to the processor to retrieve additional terms related to search terms, a data store holding social media information, and a processor configured to identify influential nodes and links based on user feedback, supporting real-time updates and graphical depiction of network data.

Motif recognition in graph data derived from noise reduced social media data

A method involving compression of uncompressed graphs, appending compressed graphs to similar graphs, counting canonical representations of graphs, generating random graphs for comparison, and computing a distribution score to determine motif significance, thereby enabling discovery of significant subgraph patterns in noise reduced social network data.

The independent claims cover methods and systems that interactively refine search terms and retrieved data using user feedback to identify influential social network nodes and links, use specific algorithms like Linear Submodular Bandits and Latent Dirichlet Allocation, implement real-time iterative analysis, and extend motif recognition using compressed graph representations for significant pattern detection.

Stated Advantages

Accelerates processing of large and noisy social media data streams for time-critical intelligence problems.

Enables automated extraction of implicit and explicit network links that are otherwise impractical to identify manually.

Provides interactive, user-feedback driven noise reduction allowing tractable data sets without significant loss of relevant results.

Supports substantially real-time iteration and updating of influence scores and network links using scalable parallel computing frameworks.

Improves performance over traditional offline learning methods by using online learning algorithms for incremental data processing.

Allows discovery of larger and more significant network motifs through efficient graph compression and canonical form analysis.

Documented Applications

Processing social media data streams such as Twitter, Reddit, and Facebook for intelligence analysis.

Predicting box office rankings of movies over specified time periods using motif analysis on social network data.

Predicting end-of-month stock price changes for selected common stocks using social media-based network motif detection.

JOIN OUR MAILING LIST

Stay Connected with MTEC

Keep up with active and upcoming solicitations, MTEC news and other valuable information.