From biological to social networks: Link prediction based on multi-way spectral clustering
MetadataShow full item record
SubjectBioinformatics databases; Cross-disciplinary applications; Clustering; Information filtering
Link prediction in protein-protein interaction networks (PPINs) is an important task in biology, since the vast majority of biological functions involve such protein interactions. Link prediction is also important for online social networks (OSNs), which provide predictions about who is a friend of whom. Many link prediction methods for PPINs/OSNs are local-based and do not exploit all network structure, which limits prediction accuracy. On the other hand, there are global approaches to detect the overall path structure in a network, being computationally prohibitive for huge-size PPINs/OSNs. In this paper, we enhance a previously proposed multi-way spectral clustering method by introducing new ways to capture node proximity in both PPINs/OSNs. Our new enhanced method uses information obtained from the top few eigenvectors of the normalized Laplacian matrix. As a result, it produces a less noisy matrix, which is smaller and more compact than the original one. In this way, we are able to provide faster and more accurate link predictions. Moreover, our new spectral clustering model is based on the well-known Bray-Curtis coefficient to measure proximity between two nodes. Compared to traditional clustering algorithms, such as k-means and DBSCAN, which assume globular (convex) regions in Euclidean space, our approach is more flexible in capturing the non-connected components of a social graph and a wider range of cluster geometries. We perform an extensive experimental comparison of the proposed method against existing link prediction algorithms and k-means algorithm, using two synthetic data sets, three real social networks and three real human protein data sets. Our experimental results show that our SpectralLink algorithm outperforms the local approaches, the k-means algorithm and another spectral clustering method in terms of effectiveness, whereas it is more efficient than the global approaches. © 2013 Elsevier B.V. All rights reserved.
Showing items related by title, author, creator and subject.
Affordable and Energy-Efficient Cloud Computing Clusters: The Bolzano Raspberry Pi Cloud Cluster Experiment Abrahamsson P; Helmer S; Phaphoom N; Nicolodi L; Preda N; Miori L; Angriman M; Rikkilä J; Wang X; Hamily K; Bugoloni S (IEEE, 2013)We present our ongoing work building a Raspberry Pi cluster consisting of 300 nodes. The unique characteristics of this single board computer pose several challenges, but also offer a number of interesting opportunities. ...
Technical, Financial, and Social Barriers and Challenges in Deep Building Renovation: Integration of Lessons Learned from the H2020 Cluster Projects D’Oca S; Ferrante A; Ferrer C; Pernetti R; Gralka A; Sebastian R; Op ‘t Veld P (2018)With a low rate of new building construction and an insufficient rate of existing building renovation, there is the need to step up the pace of building renovation with ambitious performance targets to achieve European ...
Lango Allen H; Estrada K; Lettre G; Berndt SI; Weedon MN; Rivadeneira F; Willer CJ; Jackson AU; Vedantam S; Raychaudhuri S; Ferreira T; Wood AR; Weyant RJ; Segrè AV; Speliotes EK; Wheeler E; Soranzo N; Park JH; Yang J; Gudbjartsson D; Heard-Costa NL; Randall JC; Qi L; Vernon Smith A; Mägi R; Pastinen T; Liang L; Heid IM; Luan J; Thorleifsson G; Winkler TW; Goddard ME; Sin Lo K; Palmer C; Workalemahu T; Aulchenko YS; Johansson A; Zillikens MC; Feitosa MF; Esko T; Johnson T; Ketkar S; Kraft P; Mangino M; Prokopenko I; Absher D; Albrecht E; Ernst F; Glazer NL; Hayward C; Hottenga JJ; Jacobs KB; Knowles JW; Kutalik Z; Monda KL; Polasek O; Preuss M; Rayner NW; Robertson NR; Steinthorsdottir V; Tyrer JP; Voight BF; Wiklund F; Xu J; Zhao JH; Nyholt DR; Pellikka N; Perola M; Perry JR; Surakka I; Tammesoo ML; Altmaier EL; Amin N; Aspelund T; Bhangale T; Boucher G; Chasman DI; Chen C; Coin L; Cooper MN; Dixon AL; Gibson Q; Grundberg E; Hao K; Juhani Junttila M; Kaplan LM; Kettunen J; König IR; Kwan T; Lawrence RW; Levinson DF; Lorentzon M; McKnight B; Morris AP; Müller M; Suh Ngwa J; Purcell S; Rafelt S; Salem RM; Salvi E; Sanna S; Shi J; Sovio U; Thompson JR; Turchin MC; Vandenput L; Verlaan DJ; Vitart V; White CC; Ziegler A; Almgren P; Balmforth AJ; Campbell H; Citterio L; De Grandi A; Dominiczak A; Duan J; Elliott P; Elosua R; Eriksson JG; Freimer NB; Geus EJ; Glorioso N; Haiqing S; Hartikainen AL; Havulinna AS; Hicks AA; Hui J; Igl W; Illig T; Jula A; Kajantie E; Kilpeläinen TO; Koiranen M; Kolcic I; Koskinen S; Kovacs P; Laitinen J; Liu J; Lokki ML; Marusic A; Maschio A; Meitinger T; Mulas A; Paré G; Parker AN; Peden JF; Petersmann A; Pichler I; Pietiläinen KH; Pouta A; Ridderstråle M; Rotter JI; Sambrook JG; Sanders AR; Schmidt CO; Sinisalo J; Smit JH; Stringham HM; Bragi Walters G; Widen E; Wild SH; Willemsen G; Zagato L; Zgaga L; Zitting P; Alavere H; Farrall M; McArdle WL; Nelis M; Peters MJ; Ripatti S; van Meurs JB; Aben KK; Ardlie KG; Beckmann JS; Beilby JP; Bergman RN; Bergmann S; Collins FS; Cusi D; den Heijer M; Eiriksdottir G; Gejman PV; Hall AS; Hamsten A; Huikuri HV; Iribarren C; Kähönen M; Kaprio J; Kathiresan S; Kiemeney L; Kocher T; Launer LJ; Lehtimäki T; Melander O; Mosley TH; Musk AW; Nieminen MS; O'Donnell CJ; Ohlsson C; Oostra B; Palmer LJ; Raitakari O; Ridker PM; Rioux JD; Rissanen A; Rivolta C; Schunkert H; Shuldiner AR; Siscovick DS; Stumvoll M; Tönjes A; Tuomilehto J; van Ommen GJ; Viikari J; Heath AC; Martin NG; Montgomery GW; Province MA; Kayser M; Arnold AM; Atwood LD; Boerwinkle E; Chanock SJ; Deloukas P; Gieger C; Grönberg H; Hall P; Hattersley AT; Hengstenberg C; Hoffman W; Lathrop GM; Salomaa V; Schreiber S; Uda M; Waterworth D; Wright AF; Assimes TL; Barroso I; Hofman A; Mohlke KL; Boomsma DI; Caulfield MJ; Cupples LA; Erdmann J; Fox CS; Gudnason V; Gyllensten U; Harris TB; Hayes RB; Jarvelin MR; Mooser V; Munroe PB; Ouwehand WH; Penninx BW; Pramstaller PP; Quertermous T; Rudan I; Samani NJ; Spector TD; Völzke H; Watkins H; Wilson JF; Groop LC; Haritunians T; Hu FB; Kaplan RC; Metspalu A; North KE; Schlessinger D; Wareham NJ; Hunter DJ; O'Connell JR; Strachan DP; Wichmann HE; Borecki IB; van Duijn CM; Schadt EE; Thorsteinsdottir U; Peltonen L; Uitterlinden AG; Visscher PM; Chatterjee N; Loos RJ; Boehnke M; McCarthy MI; Ingelsson E; Lindgren CM; Abecasis GR; Stefansson K; Frayling TM; Hirschhorn JN (2010)Most common human traits and diseases have a polygenic pattern of inheritance: DNA sequence variants at many genetic loci influence the phenotype. Genome-wide association (GWA) studies have identified more than 600 variants ...