PDF Publication Title:
Text from PDF Page: 160
136 we propose a metric based on the widely adopted metric conductance [71]. Let G = (V, E) denote a graph, let A ⊂ V be a subset of the vertices that forms a community, and let B = V \A. Let us also define eAB to be the number of edges between A and B and eAA as the number of edges within A. The conductance of A is then traditionally defined as eAB/eAA. Therefore, a small value of conductance denotes a strong community, as the community would be tightly linked internally, with very few links to the rest of the graph. However, this definition of conductance is not a good measure for the “goodness” of a community, as it is biased towards large communities. For example, if we place all the vertices in the graph in a single community, the conductance would be 0, which does not provide any information about the community formed. Hence, we propose a new metric called normalized conductance. To derive nor- malized conductance, we first define the value K of community A as K= eAA (7.3) eAA + eAB This value is similar to conductance, except that it ranges between 0 and 1. A measure close to zero indicates very poor community structure, and a measure close to 1 indicates very good community structure with many more links within A than to the outside. However, this metric is still not perfect, as very large communities are naturally biased towards having many more edges within the graph (high eAA). Thus, we define the normalized conductance C for a community A as K minus the expected value of K for a random graph with the same communities A and B.PDF 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 | RSS | AMP |