Machine Learning/Kaggle Social Network Contest/Features

TODO

• Precisely define the listed features

Possible Features

• Node Features
  • nodeid
  • outdegree
  • indegree
  • local clustering coefficient
  • reciprocation of inbound probability (num of edges returned / num of inbound edges)
  • reciprocation of outbound probability (num of edges returned / num of outbound edges)

• Edge Features
  • nodetofollowid
  • shortest distance nodeid to nodetofollowid
  • density? (median path length)
  • does reverse edge exist? (aka is nodetofollowid following nodeid?)
  • number of common friends
  • indegrees & outdegrees of nodetofollowid

• Network features
  • unweighted random walk score
  • global clustering coefficient
  • Adamic-Adar score
    • see original paper
    • R igraph: similarity.invlogweighted

• Clustering
  • membership of the same strongly connected cluster
    • using igraph clusters

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:

1. is there a directed edge from t to s?
2. the in-degree of s
3. the out-degree of s
4. the in-degree of t
5. the out-degree of t
6. RLD_-1(s)
7. RLD₁(s)
8. RLD₀(s)
9. RLD_-1(t)
10. RLD₁(t)
11. RLD₀(t)
12. AA₀¹(s,t)
13. AA₀^1.5(s,t)
14. AA₀²(s,t)
15. AA_-1¹(s,t)
16. AA_-1^1.5(s,t)
17. AA_-1²(s,t)
18. AA₁¹(s,t)
19. AA₁^1.5(s,t)
20. AA₁²(s,t)

where

• RLD_x(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_x^h(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_x^h(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_x^h(s,t) = (N_x^h(s) ∩ N_-x^h(t)) \ ∪_{h' < h} (N_x^h'(s) ∩ N_-x^h'(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_x^h(s,t) are distinct for different h.
• It is directional, ie sometimes C_x^h(s,t)≠C_x^h(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_x^h(s,t) = sum_{n ∈ Cx^h(s,t)} RLD₀(n)