Inferring the location of users in online social media platforms using social network analysis

• US 9,794,358 B1
• Filed: 03/13/2014
• Issued: 10/17/2017
• 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: Jurgens, David A.
• Primary Examiner(s): Parry, Chris
• Assistant Examiner(s): Hlaing, Soe M
• Application Number:
  US14/210,265
• Publication Number:
  US 20170310772A1
• Time in Patent Office: 1,314 Days
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

Described is a system for inferring the location of users in online social media platforms using social network analysis. A social network is first extracted from data from at least one social media platform. A mapping is generated from each user to the user'"'"'s estimated geographical location in the social network, resulting in an estimated location mapping. A mapping is generated from each user to the user'"'"'s known geographical location, if known, resulting in a known location mapping. The estimated location mapping is updated to match the known location mapping. The location for each user j in the known location mapping is updated in a current estimated location mapping. The final geographical locations of users connected with j are estimated using a geometric median metric. Finally, the final estimated geographical locations of users connected with j are mapped into the social network.

Claims

1. A system for inferring the location of users of online social media platforms, the system comprising:

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

(a) extracting a social network from data from at least one social media platform, wherein the social network comprises a plurality of users connected through social relationships, and wherein each user in the plurality of users has an identity on each social media platform;

(b) generating a mapping in the social network from each user in the plurality of users to the user'"'"'s estimated geographical location, resulting in an estimated location mapping Est;

(c) generating a mapping in the social network from each user in the plurality of users having known geographical location data to the user'"'"'s known geographical location, resulting in a known location mapping SL;

(d) updating the estimated location mapping Est to have the same mapping as the known location mapping SL;

(e) for a user j in the plurality of users having a mapping in the known location mapping SL, updating the location of j in Est′

to be the location in the known location mapping SL, wherein Est′

is an updated individual-location mapping for a current iteration;

(f) repeating operation (e) for each user in the plurality of users;

wherein N is a set of users having a social relationship with user j, and wherein NL is a set of locations;

(g) for each user k in N having a mapping in Est, adding the estimated geographical location of k in Est to NL;

(h) estimating a new geographical location of j using a geometric median metric;

(i) updating Est′

with the new geographical location of j;

(j) iterating through operations (e) through (h) until a stopping criteria is met, wherein the stopping criteria is one of a fixed number of iterations, a number of users who have been located, and a percentage change in users with new geographical locations;

(k) replacing the mappings in Est with those in Est′

; and

(l) mapping users to final, estimated locations based on the mappings in Est.

2. The system as set forth in claim 1, wherein the one or more processors further perform an operation of:

providing a subgraph of the social network for N and the set of locations NL.

3. The system as set forth in claim 2, wherein the one or more processors further perform an operation of combining a user'"'"'s identities from all social media platforms, such that each user is represented as a single individual in the social network.

4. The system as set forth in claim 3, wherein the one or more processors further perform an operation of merging estimated geographical location data and known geographical location data from all social media platforms for a user.

5. The system as set forth in claim 4, wherein the one or more processors further perform an operation of selecting only those users in N who also have social relationships with each other for geographical location estimation using the geometric median metric.

6. A computer-implemented method for inferring the location of users of online social media platforms, comprising an act of:

causing one or more processors to execute instructions stored on a non-transitory memory such that upon execution, the one or more processors performs operations of;

(a) extracting a social network from data from at least one social media platform, wherein the social network comprises a plurality of users connected through social relationships, and wherein each user in the plurality of users has an identity on each social media platform;

(b) generating a mapping in the social network from each user in the plurality of users to the user'"'"'s estimated geographical location, resulting in an estimated location mapping Est;

(c) generating a mapping in the social network from each user in the plurality of users having known geographical location data to the user'"'"'s known geographical location, resulting in a known location mapping SL;

(d) updating the estimated location mapping Est to have the same mapping as the known location mapping SL;

(e) for a user j in the plurality of users having a mapping in the known location mapping SL, updating the location of j in Est′

to be the location in the known location mapping SL, wherein Est′

is an updated individual-location mapping for a current iteration;

(f) repeating operation (e) for each user in the plurality of users;

wherein N is a set of users having a social relationship with user j, and wherein NL is a set of locations;

(g) for each user k in N having a mapping in Est, adding the estimated geographical location of k in Est to NL;

(h) estimating a new geographical location of j using a geometric median metric;

(i) updating Est′

with the new geographical location of j;

(j) iterating through operations (e) through (h) until a stopping criteria is met, wherein the stopping criteria is one of a fixed number of iterations, a number of users who have been located, and a percentage change in users with new geographical locations;

(k) replacing the mappings in Est with those in Est′

; and

(l) mapping users to final, estimated locations based on the mappings in Est.

7. The method as set forth in claim 6, wherein the one or more processors further performs an operation of:

providing a subgraph of the social network for N and the set of locations NL.

8. The method as set forth in claim 7, wherein the one or more processors further performs an operation of combining a user'"'"'s identities from all social media platforms, such that each user is represented as a single individual in the social network.

9. The method as set forth in claim 8, wherein the one or more processors further performs an operation of merging estimated geographical location data and known geographical location data from all social media platforms for a user.

10. The method as set forth in claim 9, wherein the one or more processors further performs an operation of selecting only those users in N who also have social relationships with each other for geographical location estimation using the geometric median metric.

11. A computer program product for inferring the location of users of online social media platforms, 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:

(a) extracting a social network from data from at least one social media platform, wherein the social network comprises a plurality of users connected through social relationships, and wherein each user in the plurality of users has an identity on each social media platform;

(b) generating a mapping in the social network from each user in the plurality of users to the user'"'"'s estimated geographical location, resulting in an estimated location mapping Est;

(c) generating a mapping in the social network from each user in the plurality of users having known geographical location data to the user'"'"'s known geographical location, resulting in a known location mapping SL;

(d) updating the estimated location mapping Est to have the same mapping as the known location mapping SL;

(e) for a user j in the plurality of users having a mapping in the known location mapping SL, updating the location of j in Est′

to be the location in the known location mapping SL, wherein Est′

is an updated individual-location mapping for a current iteration;

(f) repeating operation (e) for each user in the plurality of users;

wherein N is a set of users having a social relationship with user j, and wherein NL is a set of locations;

(g) for each user k in N having a mapping in Est, adding the estimated geographical location of k in Est to NL;

(h) estimating a new geographical location of j using a geometric median metric;

(i) updating Est′

with the new geographical location of j;

(j) iterating through operations (e) through (h) until a stopping criteria is met, wherein the stopping criteria is one of a fixed number of iterations, a number of users who have been located, and a percentage change in users with new geographical locations;

(k) replacing the mappings in Est with those in Est′

; and

(l) mapping users to final, estimated locations based on the mappings in Est.

12. The computer program product as set forth in claim 11, further comprising instructions for causing the processor to perform an operation of:

providing a subgraph of the social network for N and the set of locations NL.

13. The computer program product as set forth in claim 12, further comprising instructions for causing the processor to perform an operation of combining a user'"'"'s identities from all social media platforms, such that each user is represented as a single individual in the social network.

14. The computer program product as set forth in claim 13, further comprising instructions for causing the processor to perform an operation of merging estimated geographical location data and known geographical location data from all social media platforms for a user.

15. The computer program product as set forth in claim 14, further comprising instructions for causing the processor to perform an operation of selecting only those users in N who also have social relationships with each other for geographical location estimation using the geometric median metric.