Tie persistence analysis

From Cohen Courses
Jump to navigationJump to search

Related Work

  • Structure and tie strengths in mobile communication network - Onnela, Barabasi - PNAS 2007
   In this paper they studied coupling between tie strengths and local network structure.
   They also compared information diffusion through strong ties with the same through weak ties.
  • The dynamics of a mobile phone network - Hidalgo et. al. ScienceDirect Jan 2008
   They studied the relation between structure of mobile network and link persistence
   They proposed rule based prediction technique to predict which ties will remain in future.


Problem Formulation

  • We divided the 6 months of phone call data into time panels of period 15 days each. 
  • Given the links and network structure in panel 1, we predict which links will persist in panels 2,3,4 etc.

Time panel.png


Term definitions

  • Tie persistence: It is the stability of ties across time as number of panels in which a link is observed, over the total number of panels.

Pij = Sum_t (Aij(t)/m),

where Pij is the persistence of tie eij , Aij is 1 if users i and j communicated in time panel t and 0 otherwise, and m is the total number of panels.

  • User perseverance: Perseverance of a user is defined as the average of the persistences of all his/her ties.

Pi = 1/Ki Sum_j (Pij) , where Pi is the perseverance of user i, Ki is i’s degree (number of neighbors), and Pij is the persistence of tie eij as defined above.

  • Tie Attributes
 * Reciprocity (R): R is a Boolean attribute which denotes whether the tie between i and j is reciprocated during a given time period. That is, R is 1 if both edges eij and eji exist, and 0 otherwise.
 * Topological Overlap (TO): 
  TO(i, j)= sqrt(Oi,j^2 / (Ki * Kj)), where Oi,j is the number of common neighbors of
  node i and node j, and Ki denotes the degree of node i.
  • Node Attributes
  * Degree (K): Ki denotes the number of neighbors of a given node i.
  * Cluster Coefficient (C): 
    Ci = 2 (num triangles node i is part of) / Ki * (Ki−1)
  * User Reciprocity (r): ri the fraction of ties of a

given user i that are reciprocated.

Methodology

  • We first find the correlation between different tie attributes and Link persistence. We use Pearson correlation coefficient to measure this.
  • We also find correlation between node attributes and user perseverence.
  • For predicting whether a link in panel 1 will persist in future panel, we divide the data into train and test.
  • We then learn Logistic regression function for the tie persistence using train data and we measure the F1 accuracy of the learnt model on test data.
  • We also compare results with rule based system proposed in earlier work.

Conclusions

  • Local network attributes such as clustering coefficient and tie attributes such as reciprocity help to predict whether ties will persist in the future.
  • Our prediction results using logistic regression show that tie attributes give better accuracy than node attributes and using both types of attributes together yields the best prediction accuracy.
  • Regression techniques give better accuracy than rule based techniques.