000222510 001__ 222510
000222510 005__ 20190317000545.0
000222510 0247_ $$2doi$$a10.5075/epfl-thesis-7279
000222510 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis7279-3
000222510 02471 $$2nebis$$a10740814
000222510 037__ $$aTHESIS 000222510 041__$$aeng
000222510 088__ $$a7279 000222510 245__$$aNetwork Alignment: Theory, Algorithms, and Applications
000222510 269__ $$a2016 000222510 260__$$aLausanne$$bEPFL$$c2016
000222510 300__ $$a215 000222510 336__$$aTheses
000222510 502__ $$aProf. Boi Faltings (président) ; Prof. Matthias Grossglauser (directeur de thèse) ; Prof. Patrick Thiran, Prof. Mark Crovella, Prof. Negar Kiyavash (rapporteurs) 000222510 520__$$aNetworks are central in the modeling and analysis of many large-scale human and technical systems, and they have applications in diverse fields such as computer science, biology, social sciences, and economics. Recently, network mining has been an active area of research. In this thesis, we study several related network-mining problems, from three different perspectives: the modeling and theory perspective, the computational perspective, and the application perspective. In the bulk of this thesis, we focus on network alignment, where the data provides two (or more) partial views of the network, and where the node labels are sometimes ambiguous. Network alignment has applications in social-network reconciliation and de-anonymization, protein-network alignment in biology, and computer vision.  In the first part of this thesis, we investigate the feasibility of network alignment with a random-graph model. This random-graph model generates two (or several) correlated networks, and  lets the two networks to overlap only partially. For a particular alignment, we define a cost function for structural mismatch. We show that the minimization of the proposed cost function (assuming that we have access to infinite computational power), with high probability, results in an alignment that recovers the set of shared nodes between the two networks, and that also recovers the true matching between the shared nodes.  The most scalable network-alignment approaches use ideas from percolation theory, where a matched node-couple infects its neighboring couples that are additional potential matches. In the second part of this thesis, we propose a new percolation-based network-alignment algorithm that can match large networks by using only the network structure and a handful of initially pre-matched node-couples called seed set. We characterize a phase transition in matching performance as a function of the seed-set size.  In the third part of this thesis, we consider two important application areas of network mining in biology and public health. The first application area is percolation-based network alignment of protein-protein interaction (PPI) networks in biology. The alignment of biological networks has many uses, such as the detection of conserved biological network motifs, the prediction of protein interactions, and the reconstruction of phylogenetic trees. Network alignment can be used to transfer biological knowledge between species. We introduce a new global pairwise-network alignment algorithm for PPI networks, called PROPER. The PROPER algorithm shows higher accuracy and speed compared to other global network-alignment methods. We also extend PROPER to the global multiple-network alignment problem. We introduce a new algorithm, called MPROPER, for matching multiple networks. Finally, we explore IsoRank, one of the first and most referenced global pairwise-network alignment algorithms.  Our second application area is the control of epidemic processes. We develop and model strategies for mitigating an epidemic in a large-scale dynamic contact network. More precisely, we study epidemics of infectious diseases by (i) modeling the spread of epidemics on a network by using many pieces of information about the mobility and behavior of a population; and by (ii) designing personalized behavioral recommendations for individuals, in order to mitigate the effect of epidemics on that network.
000222510 6531_ $$aNetwork mining 000222510 6531_$$anetwork alignment
000222510 6531_ $$agraph matching 000222510 6531_$$arandom graph
000222510 6531_ $$apercolation 000222510 6531_$$aprotein-protein interaction
000222510 6531_ $$aepidemic modeling 000222510 700__$$0245634$$aKazemi, Ehsan$$g199713
000222510 720_2 $$0241029$$aGrossglauser, Matthias$$edir.$$g152655
000222510 8564_ $$s3248550$$uhttps://infoscience.epfl.ch/record/222510/files/EPFL_TH7279.pdf$$yn/a$$zn/a
000222510 909C0 $$0252455$$pLCA4$$xU10836 000222510 909CO$$ooai:infoscience.tind.io:222510$$pthesis-bn2018$$pDOI$$pIC$$pthesis$$qDOI2$$qGLOBAL_SET
000222510 917Z8 $$x108898 000222510 917Z8$$x108898
000222510 917Z8 $$x108898 000222510 918__$$aIC$$dEDIC 000222510 919__$$aLCA4
000222510 920__ $$a2016-11-2$$b2016
000222510 970__ $$a7279/THESES 000222510 973__$$aEPFL$$sPUBLISHED 000222510 980__$$aTHESIS