Per-user accuracy measure for social network based geocoding algorithms

• US 10,726,090 B1
• Filed: 11/12/2014
• Issued: 07/28/2020
• Est. Priority Date: 04/05/2013
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Compton, Ryan F., Allen, David L.
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Dewan, Kamal K
• Application Number:
  US14/539,828
• Time in Patent Office: 2,085 Days
• Field of Search: 707741, 707751, 707999101, 707E17109, 715751
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: H04L 12/1831 Tracking arrangements for later retrieval, e.g. recording contents, participants activities or behavior, network status
• CPC Class Codes: H04L 51/046 Interoperability with other network applications or services
• CPC Class Codes: H04L 51/222 using geographical location information, e.g. messages transmitted or received in proximity of a certain spot or area
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Described is a system for geocoding social networks by minimizing total variation. A set of social media data from a social media platform having users is received. A social network is generated from the set of social media data based on communication between users. A ground truth set of locations is determined for users who make their locations public, and the ground truth set of locations is propagated across the social network to generate a location estimate for each user. A confidence measure for each location estimate is then generated.

Claims

1. A system for geocoding social networks, the system comprising:

one or more processors and a non-transitory computer-readable medium having executable instructions encoded thereon such that when executed, the one or more processors perform operations of;

receiving a set of social media data from a social media platform having users;

generating a social network from the set of social media data based on communication between users on the social media platform;

determining a ground truth set of locations for users who make their locations public;

propagating the ground truth set of locations across the social network to generate a location estimate for each user by employing a parallel coordinate descent technique to solve a globally-defined total variation-based optimization problem;

generating a confidence measure for each location estimate;

reporting a geolocation of a user with a previously unknown location to an outside agency with an interest in preventing social unrest; and

wherein the globally-defined total variation-based optimization problem is as follows;

4. The system as set forth in claim 1, wherein in generating the social network, the social network is generated from the set of social media data based on bi-directional communication between users having a mutual friend on the social media platform.

5. The system as set forth in claim 4, wherein the bi-directional communication is based on reciprocated @mentions on the social media platform.

6. The system as set forth in claim 1, wherein the one or more processors further perform an operation of propagating the ground truth set of locations by calculating an optimization based on geodesic distance and graph connectivity between each user.

7. The system as set forth in claim 1, wherein the confidence measure is calculated based on deviations of location estimates for a user'"'"'s contacts.

2. A computer-implemented method for geocoding social networks, comprising:

an act of causing a data processor to execute instructions stored on a non-transitory memory such that upon execution, one or more processors perform operations of;

receiving a set of social media data from a social media platform having users;

generating a social network from the set of social media data based on communication between users on the social media platform;

determining a ground truth set of locations for users who make their locations public;

propagating the ground truth set of locations across the social network to generate a location estimate for each user by employing a parallel coordinate descent technique to solve a globally-defined total variation-based optimization problem;

generating a confidence measure for each location estimate;

reporting a geolocation of a user with a previously unknown location to an outside agency with an interest in preventing social unrest; and

wherein the globally-defined total variation-based optimization problem is as follows;

3. A computer program product for geocoding social networks, the computer program product comprising computer-readable instructions stored on a non-transitory computer-readable medium that are executable by a computer having a processor for causing the processor to perform operations of:

receiving a set of social media data from a social media platform having users;

generating a social network from the set of social media data based on communication between users on the social media platform;

determining a ground truth set of locations for users who make their locations public;

propagating the ground truth set of locations across the social network to generate a location estimate for each user by employing a parallel coordinate descent technique to solve a globally-defined total variation-based optimization problem;

generating a confidence measure for each location estimate;

reporting a geolocation of a user with a previously unknown location to an outside agency with an interest in preventing social unrest; and

wherein the globally-defined total variation-based optimization problem is as follows;