跳至主要内容

Introduction to Label Propagation Algorithm 


Introduction to Label propagation algorithm (finding community structure in social networks)

Problem description:
Given a network or graph, how can you find the communities in this network. Although there is no precise definition about community, it basically means densely connected component in the network and loosely connected between different  communities.

Input: A social network N or a graph with nodes and links between them or an adjacent matrix.
Output: A vector, in which each index represents each node in the network N and the value each index points represents which community the node belongs to.

Algorithm:
1. initialization by assigning an unique label to each node in N
2. while the algorithm is not convergent, (convergence means every node does not change its label or the running times has reached the maximum number)
3.  for each node
4.      takes the label with the maximum number of neighbors have


Advantages:
Scalable: its running time is O(m), where m is the number of edges in the network.
Parallel: we can synchronously update the labels of nodes.

Disadvantages: Oscillation, which means in a bipartite network, if the left side nodes belong to the single community and the right side nodes belong to another 
single community, then the labels of two communities will switch between each other.

评论

发表评论

此博客中的热门博文

WEEKLY ADDRESS: Making Higher Education More Affordable for the Middle Class

Remarks of President Barack Obama Weekly Address The White House August 24, 2013 Video Hi, everybody.  Over the past month, I’ve been visiting towns across America, talking about what our country needs to do to secure a better bargain for the middle class.  This week, I met with high school and college students in New York and Pennsylvania to discuss the surest path to the middle class – some form of higher education. But at a moment when a higher education has never been more important, it’s also never been more expensive.  That’s why, over the past four years, we’ve helped make college more affordable for millions of students and families with grants and loans that go farther from before. But students and families and taxpayers cannot just keep subsidizing college costs that keep going up and up.  Not when the average student now graduates more than $26,000 in debt. We cannot price the middle class out of a college education.  That’s why I pro...
发表评论
阅读全文

WEEKLY ADDRESS: Let’s Get Back to the Work of the American People

Remarks   of   President   Barack   Obama   Weekly   Address The   White   House October  12, 2013 video Good   morning . Over   the   past   few   days ,  I ’ ve   met   with   Republicans   and   Democrats   from   both   houses   of   Congress  in   an   effort   to   reopen   your   government   and   remove   the   dangers   of   default   from   our   economy . It ’ s   a   positive   development   that   House   Republicans   have   agreed   on   the   need   to   avoid   the  economic   consequences   of   not   meeting   our   country ’ s   commitments .  Because   once   the   debt   ceiling  is   raised ,  and   ...
发表评论
阅读全文

WEEKLY ADDRESS: Calling for Limited Military Action in Syria

Remarks of President Barack Obama Weekly Address The White House September 7, 2013 Video Almost three weeks ago in Syria, more than 1,000 innocent people – including hundreds of children – were murdered in the worst chemical weapons attack of the 21 st  century.  And the United States has presented a powerful case to the world that the Syrian government was responsible for this horrific attack on its own people. This was not only a direct attack on human dignity; it is a serious threat to our national security.  There’s a reason governments representing 98 percent of the world’s people have agreed to ban the use of chemical weapons.  Not only because they cause death and destruction in the most indiscriminate and inhumane way possible – but because they can also fall into the hands of terrorist groups who wish to do us harm. That’s why, last weekend, I announced that, as Commander in Chief, I decided that the United States should take military action...
发表评论
阅读全文