Hierarchical clustering of networks

Hierarchical clustering is one method for finding community structures in a network. The technique arranges the network into a hierarchy of groups according to a specified weight function. The data can then be represented in a tree structure known as a dendrogram. Hierarchical clustering can either be agglomerative or divisive depending on whether one proceeds through the algorithm by adding links to or removing links from the network, respectively. One divisive technique is the Girvan–Newman algorithm.

Algorithm

In the hierarchical clustering algorithm, a weight is first assigned to each pair of vertices in the network. The weight, which can vary depending on implementation (see section below), is intended to indicate how closely related the vertices are. Then, starting with all the nodes in the network disconnected, begin pairing nodes from highest to lowest weight between the pairs (in the divisive case, start from the original network and remove links from lowest to highest weight). As links are added, connected subsets begin to form. These represent the network's community structures.

The components at each iterative step are always a subset of other structures. Hence, the subsets can be represented using a tree diagram, or dendrogram. Horizontal slices of the tree at a given level indicate the communities that exist above and below a value of the weight.

Weights

There are many possible weights for use in hierarchical clustering algorithms. The specific weight used is dictated by the data as well as considerations for computational speed. Additionally, the communities found in the network are highly dependent on the choice of weighting function. Hence, when compared to real-world data with a known community structure, the various weighting techniques have been met with varying degrees of success.

Two weights that have been used previously with varying success are the number of node-independent paths between each pair of vertices and the total number of paths between vertices weighted by the length of the path. One disadvantage of these weights, however, is that both weighting schemes tend to separate single peripheral vertices from their rightful communities because of the small number of paths going to these vertices. For this reason, their use in hierarchical clustering techniques is far from optimal.[1]

Edge betweenness centrality has been used successfully as a weight in the Girvan–Newman algorithm.[1] This technique is similar to a divisive hierarchical clustering algorithm, except the weights are recalculated with each step.

The change in modularity of the network with the addition of a node has also been used successfully as a weight.[2] This method provides a computationally less-costly alternative to the Girvan-Newman algorithm while yielding similar results.

See also

References

  1. ^ a b Girvan, M.; Newman, M. E. J. (2002-06-11). "Community structure in social and biological networks". Proceedings of the National Academy of Sciences. 99 (12): 7821–7826. arXiv:cond-mat/0112110. Bibcode:2002PNAS...99.7821G. doi:10.1073/pnas.122653799. ISSN 0027-8424. PMC 122977. PMID 12060727.
  2. ^ Newman, M. E. J. (2004-06-18). "Fast algorithm for detecting community structure in networks". Physical Review E. 69 (6): 066133. arXiv:cond-mat/0309508. Bibcode:2004PhRvE..69f6133N. doi:10.1103/physreve.69.066133. ISSN 1539-3755. PMID 15244693. S2CID 301750.

Read other articles:

Grand Prix F1 Belgia 2015

Grand Prix Belgia 2015 Lomba ke-11 dari 19 dalam Formula Satu musim 2015← Lomba sebelumnyaLomba berikutnya → Tata letak sirkuit Spa-Francorchamps.Detail perlombaan[1]Tanggal 23 Agustus 2015Nama resmi 2015 Formula 1 Shell Belgian Grand Prix[1]Lokasi Sirkuit Spa-FrancorchampsStavelot, BelgiaSirkuit Fasilitas balapan permanenPanjang sirkuit 7.004 km (4.352 mi)Jarak tempuh 43 putaran, 301.048 km (187.063 mi)Rencana jarak tempuh 44 putaran, 308.052 km (191.4...

 

Virus mosaik tembakau

Virus mosaik tembakau Tobacco mosaic virus Satu unit monomer dari Virus Mosaik TembakauKomposisi genom virus ICTVpositive-sense single-stranded RNA virus (en), positive-sense single-stranded RNA virus (en) dan positive-sense single-stranded RNA virus (en) TaksonomiSuperdomainBiotaDomainVirusFamiliVirgaviridaeGenusTobamovirusSpesiesTobacco mosaic virus lbs Virus mosaik tembakau (bahasa Inggris: Tobacco mosaic virus, sering disingkat TMV) adalah virus yang menyebabkan penyakit pada tembakau dan...

 

Gerhana matahari 4 Desember 2021

Gerhana matahari 4 Desember 2021PetaJenis gerhanaJenisTotalGamma-0.9526Magnitudo1.0367Gerhana maksimumDurasi114 sec (1 m 54 s)Koordinat76°48′S 46°12′W / 76.8°S 46.2°W / -76.8; -46.2Lebar jalur maksimum419 km (260 mi)Waktu (UTC)Puncak gerhana7:34:38ReferensiSaros152 (13 of 70)Katalog # (SE5000)9556 Gerhana matahari total terjadi pada hari Sabtu, 4 Desember 2021, ketika Bulan melewati antara Bumi dan Matahari, sehingga mengaburk...

Mariposa, California

Not to be confused with Maricopa, California. Census-designated place in California, United StatesMariposaCensus-designated placeDusk in downtown MariposaLocation in Mariposa County and the state of CaliforniaMariposaShow map of CaliforniaMariposaShow map of the United StatesCoordinates: 37°29′06″N 119°57′59″W / 37.48500°N 119.96639°W / 37.48500; -119.96639Country United StatesState CaliforniaCounty MariposaArea[1] • Total4.040...

 

العلاقات الكندية الموزمبيقية

العلاقات الكندية الموزمبيقية كندا موزمبيق   كندا   موزمبيق تعديل مصدري - تعديل   العلاقات الكندية الموزمبيقية هي العلاقات الثنائية التي تجمع بين كندا وموزمبيق.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة كن�...

 

Phil Ford (basketball)

Basketball player This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Phil Ford basketball – news · newspapers · books · scholar · JSTOR (April 2021) (Learn how and when to remove this template...

Soyuz 7K-TM

Not to be confused with Soyuz-TM. Soyuz 7K-TMSoyuz 19, a Soyuz 7K-TM spacecraft, during the Apollo–Soyuz Test Project (ASTP).ManufacturerOKB-1Country of originSoviet UnionOperatorSoviet space programApplicationsCrewed spacecraft SpecificationsDimensions Height 7.48 m (24.5 ft) Diameter 2.72 m (8 ft 11 in) Volume 9 m3 (320 cu ft) RegimeLow Earth ProductionStatusRetiredLaunched5Retired5Maiden launchKosmos 6383 April 1974Last launchSoyuz 2215 September 1...

 

Diritti umani negli Stati Uniti d'America

I diritti umani negli Stati Uniti d'America trovano tutela nella Costituzione degli Stati Uniti, nel paragrafo riguardante la Carta dei Diritti, ma sono spesso sono sotto osservazione critica da parte di organizzazioni come Amnesty International e Human Rights Watch.[1] Buona parte di libertà e diritti fondamentali, ad esempio diritti civili come quello di manifestare il pensiero, la libertà religiosa e i diritti economici sulla libertà d'impresa sono tra i più ampi del mondo, men...

 

巴育·占奥差

將軍巴育·占奥差ประยุทธ์ จันทร์โอชา上將 MPCh MWM TChW 泰國樞密院議員现任就任日期2023年11月29日君主拉瑪十世議長素拉育·朱拉暖 泰國第29任總理任期2022年9月30日復職—2023年8月22日君主拉瑪十世副總理（英语：Deputy Minister of Thailand） 列表 巴威·翁素万塔那塞·巴滴玛巴功（英语：Thanasak Patimaprakorn） 威沙努·革岸（英语：Wissanu Krea-ngam） 比蒂耶�...

Egilsstaðir

Cet article est une ébauche concernant une localité islandaise. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Egilsstaðir Administration Pays Islande Région Austurland Municipalité Fljótsdalshérað Démographie Population 2 522 hab. (2020) Géographie Coordonnées 65° 15′ 50″ nord, 14° 23′ 14″ ouest Localisation Géolocalisation sur la carte : Islan...

 

PS Lampung Sakti

PS Lampung SaktiNama lengkapPersatuan Sepak bola Lampung SaktiBerdiri1962 sebagai Persires Rengat 2011 sebagai Persires Bali Devata FC 2012 sebagai Persires Cirebon FC 2013 sebagai Persires Kuningan 2014 sebagai Persires Banjarnegara 2015 sebagai Persires Sukoharjo 2016 sebagai Persires Rengat 2017 sebagai PS Lampung SaktiDibubarkan2019StadionStadion Sumpah Pemuda , Lampung, Indonesia(Kapasitas: 30.000)LigaLiga 320182 (grup 2) PS Lampung Sakti merupakan sebuah klub sepak bola Indonesia yang b...

 

Філософія

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

Berkhamsted

Town in Hertfordshire, England Not to be confused with Little Berkhamsted. Town in EnglandBerkhamstedTownBerkhamsted. From top to bottom: Berkhamsted Old Town Hall, St Peter's Church, Berkhamsted Castle, Ashridge, Berkhamsted Totem Pole and Grand Union Canal, Berkhamsted High StreetCoat of armsBerkhamstedLocation within HertfordshirePopulation18,500 (mid-2016 est.)[1]OS grid referenceSP993077DistrictDacorumShire countyHertfordshireRegionEastCountryEnglandSovereign&...

 

Candidates of the 2022 Australian federal election

2022 Australian federal election Pre-election pendulum Polling National Electorate Candidates Political parties National results House of Representatives Senate Post-election pendulum State and territory results New South Wales Victoria Queensland Western Australia South Australia Tasmania Australian Capital Territory Northern Territory vte At the close of nominations a total of 1,624 candidates had stood for the 2022 Australian federal election, of whom 1,203 were House of Representatives c...

 

Ashgabat

Capital and largest city of Turkmenistan Ashkhabad redirects here. For the Turkmen folklore band, see Ashkhabad (band). For the Second World War merchant ship, see SS Ashkhabad. For the cities in Iran, see Eshqabad (disambiguation). Capital city in TurkmenistanAshgabat AşgabatCapital cityNeutrality Road, Gypjak Mosque, Abadanchylyk Square, Independence Park, Suburbs, Urban highways SealLogoCoordinates: 37°56′15″N 58°22′48″E / 37.93750°N 58.38000°E / 37.937...

Disability in Israel

About a fifth of Israel's population is affected by disability. The country is a state party of the UN Convention on the Rights of Persons with Disabilities. There is a system of legislation and policies that protect the rights of disabled Israelis. Demographics In 2019, people with disabilities were 17% of the population of Israel. Adults from 18 to 64 years constituted 50% of the total, adults 65 years and older were 33%, and children 0–17 years old made up 17%. About 6% of working-age (...

 

Gavin & Stacey

British TV sitcom (2007–2019) Gavin & StaceyGenre Sitcom Created by James Corden Ruth Jones Written by James Corden Ruth Jones Directed byChristine GernonStarring Mathew Horne Joanna Page James Corden Ruth Jones Alison Steadman Larry Lamb Melanie Walters Rob Brydon Theme music composerStephen FretwellOpening themeRun by Stephen FretwellCountry of originUnited KingdomOriginal languageEnglishNo. of series3No. of episodes21 (list of episodes)ProductionExecutive producers Henry Normal Linds...

 

Green infrastructure

Sustainable and resilient infrastructure Runoff from the vicinity flows into an adjacent bioswale Green infrastructure or blue-green infrastructure refers to a network that provides the “ingredients” for solving urban and climatic challenges by building with nature.[1] The main components of this approach include stormwater management, climate adaptation, the reduction of heat stress, increasing biodiversity, food production, better air quality, sustainable energy production, clea...

Jung Yong-hwa

Đây là một tên người Triều Tiên, họ là Jung. Jung Yong HwaJung Yong HwaSinh22 tháng 6, 1989 (35 tuổi)Yeoksam-dong, Seoul, Hàn QuốcNghề nghiệpNhạc sĩ, Guitar, Rapper, Nhà sản xuất, Diễn viên, MC, Người mẫuSự nghiệp âm nhạcThể loạiRock, R&B, Pop, Ballad, La - tinhNhạc cụHát chính, Guitar, Clarinet, Piano, Drums, Người thu âm nhạc, Tổng hợp, BeatboxNăm hoạt động2009–nayHãng đĩaFNC EntertainmentHợp tác...

 

Scott Sharp

Questa voce sull'argomento piloti automobilistici statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Scott SharpNazionalità Stati Uniti Automobilismo CategoriaIndyCar, American Le Mans Series CarrieraCarriera nella IndyCar SeriesStagioni1996-2007, 2009 ScuderieA.J. Foyt EnterprisesKelley RacingFernández RacingRahal Letterman RacingPanther Racing Mondiali vinti1 (1996) GP disputati147 GP vinti9 Podi18 Pole position6 Statistiche aggiorn...