PDF Publication Title:
Text from PDF Page: 066
3.3.2 Global community detection One of the first community detection algorithms that did not assume pre-existing knowledge of the community structure was proposed by Girvan and Newman [119]. In short, their algorithm works by calculating the “most important” link in the network, and then removing it. The algorithm then repeats this step until the social network graph becomes partitioned, at which point the various partitions are considered as communities. Continuing to run the algorithm over the various partitions will produce even finer communities, until all of the links are removed from the network. From the above description, it is clear that the selection of the most important link is integral to the functioning of the algorithm. A good metric of importance can quickly partition the graph into its various communities, while a bad metric can simply disconnect nodes one-by-one and produce degenerate partitions. Girvan and Newman suggested using the metric of betweenness centrality. The intuition behind Girvan and Newman’s algorithm is simple: if we assume that the social network is divided into densely connected communities, the betweenness centrality metric looks for links that bridge communities. Since communities are, by definition, more dense than the graph as a whole, these bridging links will naturally have a higher betweenness centrality. Once they are removed from the graph, the underlying community structure emerges. Newman [118] later proposed a faster, alternate approach, based on the greedy optimization of modularity. The algorithm starts with each vertex in a separate community, and merges pairs of communities, choosing at each stage the pair that 42PDF Image | Online Social Networks: Measurement, Analysis, and Applications to Distributed Information Systems
PDF Search Title:
Online Social Networks: Measurement, Analysis, and Applications to Distributed Information SystemsOriginal File Name Searched:
SocialNetworks-Thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)