Communities and Balance in Signed Networks : Spectral Approach

Communities and Balance in Signed Networks : Spectral Approach

COMMUNITIES AND BALANCE IN SIGNED NETWORKS : SPECTRAL APPROACH -Pranay Anchuri*, Malik Magdon Ismail Rensselaer Polytechnic Institute, NY. OUTLINE Introduction Structural Balance Heuristic Spectral Methods Results Conclusion Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute SIGNED SOCIAL NETWORKS

Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute STRUCTURAL BALANCE Stable Notation : Unstable Negative Edge

Network is strongly balanced if all triads are stable. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Positive Edge WEAK STRUCTURAL BALANCE Stable Unstable

Network is weakly balanced if all triads are stable. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute COMMUNITIES IN BALANCED NETWORK Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Balanced network can be divided so that positive edges lie within communities negative edges between communities.

Real world networks are rarely structurally balanced. Frustration : of edges that disturb the balance. Positive edges between communities + Negative edges within communities. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Number Real world networks are rarely structurally balanced. Frustration : of edges that disturb the balance. Positive edges between communities + Negative

edges within communities. Frustration = 1 Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Number Real world networks are rarely structurally balanced. Frustration : of edges that disturb the balance. Positive edges between communities + Negative edges within communities. Frustration = 1 Pranay Anchuri, Malik Magdon Ismail,

Rensselaer Polytechnic Institute Number Real world networks are rarely structurally balanced. Frustration : of edges that disturb the balance. Positive edges between communities + Negative edges within communities. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Number Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute

Community Detection HEURISTIC Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Ignore the negative edges and cluster the remaining nodes. HEURISTIC Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute HEURISTIC Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute

Isolated nodes are added in such a way that minimizes the frustration. HEURISTIC Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Spectral Methods MINIMIZING FRUSTRATION Community C divided into C1,C2 Positive

Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute edges between C1 and C2 increase frustration. Negative edges between C1 and C2 decrease frustration. MINIMIZING FRUSTRATION Community C divided into C1,C2 Positive C2 C1 Frustration = 2 Frustration = 2

Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute edges between C1 and C2 increase frustration. Negative edges between C1 and C2 decrease frustration. MINIMIZING FRUSTRATION Community C divided into C1,C2 Positive C1 C2 Frustration = 2 Frustration = 1 Pranay Anchuri, Malik Magdon Ismail,

Rensselaer Polytechnic Institute edges between C1 and C2 increase frustration. Negative edges between C1 and C2 decrease frustration. MINIMIZING FRUSTRATION Community C divided into C1,C2 Positive C1 C2 Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute edges between C1 and C2 increase frustration.

Negative edges between C1 and C2 decrease frustration. MODULARITY Unsigned Modularity : Number Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute of edges within communities expected number if edges were randomly permuted. Measure of the surprise factor. Higher modularity is better. SIGNED MODULARITY Signed Modularity

Surprise Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute factor due to positive edges within communities and negative edges between communities. Minimizing Frustration Maximizing Modularity Both objectives reduce to maximizing ST M S Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute

COMPUTING THE MAXIMUM Maximizing f(M,S) = ST M S Optimum Requires sparse matrix vector multiplication which is efficient. S RRn Rbut Rwe Rneed RS R R{-1,+1}n R!! Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute S : Eigen vector corresponding to maximum Eigen value of M. Eigen vector can be computed by Power Iteration.

BOOLEAN SOLUTION Rounding : Based Rounding w/ Improvement : Start with an initial Boolean solution and move the nodes one at a time. If there is a sequence of flips such that solution is closer optimum then retain the changes. Complexity : O(N^2). Rounding w/ Partial Improvement: Consider zero.

nodes whose magnitude is close to Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute on sign of si, si >= 0 1 and -1 o/w. 5 7 4 3 8 0 2

1 Val in Eigen Vector 0 0.55 1 0.27 2 0.25 3 -0.44

4 -0.45 5 -0.33 6 0.10 7 0.13 8 -0.09 Pranay Anchuri, Malik Magdon Ismail,

Rensselaer Polytechnic Institute 6 Nod e 5 7 4 3 8 0 2 1 Val in Eigen

Vector 0 0.55 1 0.27 2 0.25 3 -0.44 4 -0.45

5 -0.33 6 0.10 7 0.13 8 -0.09 Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute 6

Nod e 5 7 4 3 8 0 2 1 Val in Eigen Vector 0

0.55 1 0.27 2 0.25 3 -0.44 4 -0.45 5

-0.33 6 0.10 7 0.13 8 -0.09 Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute 6 Nod e

MULTIPLE COMMUNITIES Communities can be further divided Until Change in the objective can be reduced to ST MS Also requires sparse matrix vector multiplication. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute frustration cannot be reduced. Modularity cannot be increased.

Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Results MODULARITY MAXIMIZATION Algorithm # Communities Largest Frustration (% of ve edges) Epinions.com 15 69802 175.07

Clustering (40 means) 40 59022 195.06 Modularity 15 56754 211.62 Modularity w/ partial improvement

4 117072 100 Slashdot.com Clustering ( 15 means) 15 24460 259.93 Clustering (40 means) 40

21666 288.69 Modularity 14 40378 176.85 Modularity w/ partial improvement 3 60031

141.72 Datasets obtained from http://snap.stanford.edu/ Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Clustering ( 15 means) FRUSTRATION MINIMIZATION Algorithm # Communities Largest Frustration ( % of ve edges) Epinions.com

2 74100 58.97 Two Division w/ Partial Improvement 2 73861 54.99 Multiple Division 20 69004

47.65 Multiple Division w/ Partial Improvement 23 68990 43.92 Slashdot.com Two Division 2 57824 66.34

Two Division w/ Partial Improvement 2 57853 64.71 Multiple Division 8 55479 62.52 Multiple Division w/ Partial Improvement

10 57853 60.67 Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Two Division STRONG VS WEAK BALANCE Minimum Frustration: = 1 when max # communities =2 = 0 when # communities = 3 ( each node in its own community)

Minimum frustration with multiple communities implies weak balance. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute NEGATIVE INCIDENT RATIO Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute NIR = 3/2 CONCLUSION Spectral algorithm to detect communities in signed communities. Functions : Minimizing frustration,

Maximizing frustration. Careful assignment of nodes leads to better communities. Structural balance (strong and weak) affects the communities detected. Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Objective Questions ? Pranay Anchuri, Malik Magdon Ismail, Rensselaer Polytechnic Institute Thank You

Recently Viewed Presentations

  • New Testament Survey: Book of 2 Corinthians

    New Testament Survey: Book of 2 Corinthians

    New Testament Survey: Book of 2 Corinthians See page 63… * See page 63… * See page 63, 64…Worldly sorrow brings death, but godly sorrow leads one to true repentance—not to be regretted!
  • Enunciación del sistema nominal

    Enunciación del sistema nominal

    Positiva (idem, eadem, idem / ipse, a, um). Negativa (indefinidos). is, ea, id Desinencias pronominales No tienen vocativo, excepto los posesivos. Desinencia -ius para el genitivo singular. Desinencia -i para el dativo singular. Desinencia -d para el nominativo y acusativo...
  • www.cardinalhayes.org

    www.cardinalhayes.org

    REJECTION OF NOMINALISM. Anselm of Canterbury was an extreme realist! Peter Abelard found a middle ground between realism and nominalism!
  • Title: Smoking, nicotine and tar 5th February 2015

    Title: Smoking, nicotine and tar 5th February 2015

    Title: Smoking, nicotine and tar 5th February 2015 Learning question: Why is smoking so bad for you? Aims from specification document (p) describe the effects of smoking on the mammalian gas exchange system, with reference to the symptoms of chronic...
  • Pen Knife Religion JEREMIAH 36:20-23 Pen Knife Religion

    Pen Knife Religion JEREMIAH 36:20-23 Pen Knife Religion

    Jeremiah has been continual prophesying about the coming destruction of Judah. In . Jeremiah 36:2 - God tells Jeremiah to write a book . which we now have . concerning all the words of God that He has given Jeremiah.
  • One of us? The inclusion solution Ryan Boughan

    One of us? The inclusion solution Ryan Boughan

    'Unconscious bias', using tools like the IAT (Implicit Association Test), is certainly interesting and worth knowing, but it is notoriously hard to change. A research article by 22 authors (Lai et al., 2014), spanning various universities including Harvard, investigated 17...
  • Seismic/Eruption Classroom Teaching Strategies

    Seismic/Eruption Classroom Teaching Strategies

    Arial Times New Roman Default Design Microsoft Excel Chart Slide 1 Seismic/Eruption Seismic/Eruption Features Seismic/Eruption Classroom Teaching Strategies Connections to other activities/lessons "Teachable Moment" "Teachable Moment" Student Research Projects/Questions Student Research Projects/Questions Science Fair Projects ...
  •  A series of steps that engineers use to

    A series of steps that engineers use to

    A series of steps that engineers use to guide them as they solve problems. It is cyclical and can begin at any step, or move back and forth between steps.