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...

阅读全文

Square root of a number (sqrt)

For many technical interviews in big companies, one question might be asked frequently, which is how to compute a number's square root. Based on my experience, Yahoo and Linkedin interviewers like it in the first phone screen. It looks so simple that many people would neglect some nature behind its appearance. In my blog, I will focus on the analysis part and spend some time on testing because I believe that people can not give perfect coding solution without solid analysis and sound testing cases. Let's get into it. Problem description Given you a number, compute its square root. Analysis 1) Before we start, we have to truly and totally understand what the meaning of the problem is. More importantly, in the interview process, we should know what method or technology the interviewers want us to show to them. So ask them conditions in the problem to clear ambiguities. In this case, what kind of number is as the input, integer or float? Is it a perfect square root pr...

阅读全文

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 ...

阅读全文

CS

搜索此博客