Editing Machine Learning/Kaggle Social Network Contest/Features

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
Line 3: Line 3:


== Possible Features ==
== Possible Features ==
*Node Features
*nodeid
**nodeid
*nodetofollowid
**outdegree
*median path length
**indegree
*shortest distance from nodeid to nodetofollowid
**local clustering coefficient
*inbound edges
**reciprocation of inbound probability (num of edges returned / num of inbound edges)
*outbound edges
**reciprocation of outbound probability (num of edges returned / num of outbound edges)
*clustering coefficient
*reciprocation probability (num of edges returned / num of outbound edges)


*Edge Features
The response variable is the probability that the nodeid to nodetofollowid edge will be created in the future
**nodetofollowid
**shortest distance nodeid to nodetofollowid
**density? (<strike>median path length</strike>)
**does reverse edge exist? (aka is nodetofollowid following nodeid?)
**number of common friends
**indegrees & outdegrees of nodetofollowid


From the Backstrom and Leskovec, for a node s and a potential target c
* Network features
* Network features
** unweighted random walk score
** unweighted random walk score
** global clustering coefficient
** Adamic-Adar score
** Adamic-Adar score
*** see [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.1370&rep=rep1&type=pdf original paper]
*** see [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.1370&rep=rep1&type=pdf original paper]
*** R igraph: [http://cneurocvs.rmki.kfki.hu/igraph/doc/R/similarity.html similarity.invlogweighted]
** number of common friends
 
** indegrees and outdegrees of s
* Clustering
*** the indegree is the number of edges coming into node s
** membership of the same strongly connected cluster
*** the outdegree is the number of edges leaving node s
*** using [http://cneurocvs.rmki.kfki.hu/igraph/doc/R/clusters.html igraph clusters]
** indegrees and outdegrees of c
 
The response variable is the probability that the nodeid to nodetofollowid edge will be created in the future
 
== Joe's attempt ==
I'm planning on collecting features based on an edge. Then sample the features over existing and randomly created edges and fit a logistic regression model to it.
 
For an edge from node s to node t I will calculate:
# is there a directed edge from t to s?
# the in-degree of s
# the out-degree of s
# the in-degree of t
# the out-degree of t
# RLD<sub>-1</sub>(s)
# RLD<sub>1</sub>(s)
# RLD<sub>0</sub>(s)
# RLD<sub>-1</sub>(t)
# RLD<sub>1</sub>(t)
# RLD<sub>0</sub>(t)
#AA<sub>0</sub><sup>1</sup>(s,t)
# AA<sub>0</sub><sup>1.5</sup>(s,t)
# AA<sub>0</sub><sup>2</sup>(s,t)
# AA<sub>-1</sub><sup>1</sup>(s,t)
# AA<sub>-1</sub><sup>1.5</sup>(s,t)
# AA<sub>-1</sub><sup>2</sup>(s,t)
# AA<sub>1</sub><sup>1</sup>(s,t)
# AA<sub>1</sub><sup>1.5</sup>(s,t)
# AA<sub>1</sub><sup>2</sup>(s,t)
 
where
* RLD<sub>x</sub>(n) is 1 / log(0.1 + the x-degree of node n), where -1 = in, 1 = out and 0 = any. (RLD = reciprocal log of degree )
** note that I add 0.1 so that nodes with degree 1 have a score of  1/log(1.1) = 10.49 rather than1/log(1) which is a divide by zero
** logs are taken to base e
 
I define N<sub>x</sub><sup>h</sup>(n) to be the nodes reachable from ''n'' in ''h'' hops along either any edge (x = 0), edges from t towards s (x = -1)  or edges from s towards t (x = 1).
 
I define C<sub>x</sub><sup>h</sup>(s,t) as the set of common neighbours of s and t a distance of h hops from s and t, excluding nodes in a closer common neighbourhood ie
* C<sub>x</sub><sup>h</sup>(s,t) = (N<sub>x</sub><sup>h</sup>(s) ∩ N<sub>-x</sub><sup>h</sup>(t)) \ ∪<sub>h' < h </sub>(N<sub>x</sub><sup>h'</sup>(s) ∩ N<sub>-x</sub><sup>h'</sup>(t))
** h = 1.5 corresponds to nodes which are one hop from either s or t and two hops from either t or s
* The sets C<sub>x</sub><sup>h</sup>(s,t) are distinct for different h.
* It is directional, ie sometimes C<sub>x</sub><sup>h</sup>(s,t)≠C<sub>x</sub><sup>h</sup>(t,s)
* AA is the Adamic-Adar score calculated over different common neighbourhoods.
** the subscript 0, -1, 1 referes to neighbours reachable be following any, in or out node respectively
** the superscript 1, 1.5 and 2 refer to the the number of hops from a focal node the neighbour is.
* AA<sub>x</sub><sup>h</sup>(s,t) = sum<sub>n ∈ C<sub>x</sub><sup>h</sup>(s,t)</sub> RLD<sub>0</sub>(n)
Please note that all contributions to Noisebridge are considered to be released under the Creative Commons Attribution-NonCommercial-ShareAlike (see Noisebridge:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)
Retrieved from "https://www.noisebridge.net/wiki/Machine_Learning/Kaggle_Social_Network_Contest/Features"