Network information methods devices and systems

• US 9,082,082 B2
• Filed: 12/06/2012
• Issued: 07/14/2015
• Est. Priority Date: 12/06/2011
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Jebara, Tony, Shaw, Blake, Huang, Bert
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US13/707,478
• Publication Number:
  US 20130144818A1
• Time in Patent Office: 950 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06Q 50/00 Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism healthcare informatics G16H
• CPC Class Codes: G06Q 50/02 Agriculture; Fishing; Forestry; Mining

Abstract

Methods and systems for predicting links in a network, such as a social network, are disclosed. The existing network structure can be used to optimize link prediction. The methods and systems can learn a distance metric and/or a degree preference function that are structure preserving to predict links for new/existing nodes based on node properties.

Claims

1. A method for generating proposed recommendations for new relationships in a social network and directing an output from at least one computer network server to a terminal connected thereto by a computer network, the method comprising:

storing, on a data store accessible by said at least one computer network server, profiles and links, each profile being a data set containing characteristics of a respective one of a plurality of persons, each link being a data set that corresponds to a relationship of a predefined type between one of the plurality of persons to linked one of the plurality of persons such that some of said plurality of persons are linked to first persons and unlinked to second persons, whereby each link corresponds to a linked pair of persons, the totality of links defining a network;

using said at least one computer network server, programmatically training a classifier based on distance metrics, each distance metric characterizing a respective one of said linked pairs, wherein said distance metric is responsive to outside links which are links other than said respective one of said linked pairs, such that said totality of links can be derived from said classifier based on said profiles without said links;

receiving data corresponding to a new person not linked to any other person'"'"'s links in the network and generating a new profile representing the new person; and

using said classifier, generating predicted links responsively to said new profile and outputting data responsive to said predicted links.

2. The method of claim 1, further comprising receiving relationship data from said plurality of persons and generating a new link responsive thereto, wherein said relationship data include data indicating at least one communication event between persons joined by said new link.

3. The method of claim 1, further comprising receiving relationship data from said plurality of persons and generating a new link responsive thereto, wherein said relationship data include data indicating a command received from a respective one of said plurality of persons to be connected to another of said plurality of persons.

4. The method of claim 1, wherein said distance metric is a Mahalanobis distance metric.

5. The method of claim 4, wherein the training includes minimizing an objective function using a stochastic gradient descent algorithm.

6. The method of claim 1, wherein the distance metric'"'"'s dependence on said outside links is generated responsively to the existence of said outside links and without referring to classes to which persons linked by the outside links belong, whereby structural information of said outside links is used in said predicting.

7. A computerized method for predicting links between nodes in a network using a computing device, the method comprising:

storing data representing node properties in a data storage device accessible by a processor;

storing links between the nodes in the data storage device;

each node property representing a characteristic of a person, a document, an event, web site, or other thing;

each link representing a relationship between nodes, whereby the links define a relationship network;

generating a classifier from said relationship links and said node properties using a structure preserving method adapted to, when so-generated, reproduce substantially all of said links from said node properties, whereby said classifier substantially preserves a structure defined by said links;

receiving a link prediction request from a prediction requestor, said link prediction request specifying an input node having input node properties;

predicting a plurality of new links for said input node responsively to said input node properties and said learned distance metric; and

transmitting said predicted plurality of new links to said prediction requestor.

8. The method of claim 7, wherein said generating includes modeling degree distributions embodied by said links.

9. The method of claim 7, wherein said generating is optimized using a cutting plane algorithm.

10. The method of claim 7, wherein said generating said classifier includes optimizing an objective function using a stochastic gradient descent method.

11. The method of claim 7, wherein said generating a classifier includes:

iteratively comparing triplets of said nodes, each triplet comprising a first node, a second node, and a third node, wherein said second node is linked to said first node and said third node is not linked to said first node; and

learning a distance metric generator in which for each said triplet said third node is further from said first node than said second node.

12. The method of claim 7, wherein said generating includes:

iteratively comparing triplets of said nodes, each triplet comprising a first node, a second node, and a third node, wherein said second node is linked to said first node and said third node is not linked to said first node; and

learning a distance metric in which for each said triplet said third node is further from said first node than said second node.

13. A computerized method for predicting new links in a network, the method comprising:

accessing network data from a data store, said network data including nodes and links, said nodes each having properties characterizing each node and said links each representing a connection between two of said nodes, said nodes and links comprising a network;

learning a classifier for predicting new links in said network, said learning including learning a Mahalanobis distance metric M for said network, said learning including applying one or more linear constraints on M, said constraints configured to enforce the structure of said network to be preserved in M;

receiving a link prediction request from a prediction requestor, said request indicating a target node having target properties;

predicting one or more new links for said target node responsive to said target node properties by applying a connectivity algorithm to said target node and said network nodes using said learned classifier including said learned distance metric M; and

transmitting said one or more predicted new links to said prediction requestor.

14. The method of claim 13, wherein said one or more linear constraints includes a constraint that for each of said nodes all connected nodes are closer than all unconnected nodes.

15. The method of claim 13, wherein said one or more linear constraints are enforced with slack.

16. The method of claim 13,

wherein learning a classifier for predicting new links in said network includes learning a degree preference function, said degree preference function being parameterized and non-stationary, and

wherein predicting one or more new links for said target node includes using said degree preference function to determine the number of said one or more new links to be predicted based on said target node properties.

17. The method of claim 16, wherein said learning a degree preference function includes enforcing a requirement that the resulting degree preference function for each node is concave.

18. The method of claim 13, wherein said connectivity algorithm is one of:

maximum weight b-matching, k-nearest neighbors, ε

-neighborhoods, and maximum weight spanning tree.

19. The method of claim 13, wherein said learning includes applying a Frobenius norm regularizer on M.

20. The method of claim 13, wherein said target node is a new node joining said network.