Dr. Josephine Thomas

Teamleiterin: Graphs in Artificial Intelligence and Neural Networks (GAIN)

Telefon: +49 561 804-6061
Fax: +49 561 804-6022
E-Mail: jthomas[at]uni-kassel[dot]de

Forschungsgruppe "Graphs in Artificial Intelligence and Neural Networks" (GAIN) (öffnet neues Fenster)

Publikationen

[ 2023 ]
[ 2022 ]
[ 2021 ]
[ 2017 ]
[ 2015 ]

2023[ to top ]

Power flow forecasts at transmission grid nodes using Graph Neural Networks. Beinert, Dominik; Holzhüter, Clara; Thomas, Josephine; Vogt, Stephan. In Energy and AI, 14(1), bl 100262. Elsevier, 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
The increasing share of renewable energy in the electricity grid and progressing changes in power consumption have led to fluctuating, and weather-dependent power flows. To ensure grid stability, grid operators rely on power forecasts which are crucial for grid calculations and planning. In this paper, a Multi-Task Learning approach is combined with a Graph Neural Network (GNN) to predict vertical power flows at transformers connecting high and extra-high voltage levels. The proposed method accounts for local differences in power flow characteristics by using an Embedding Multi-Task Learning approach. The use of a Bayesian embedding to capture the latent node characteristics allows to share the weights across all transformers in the subsequent node-invariant GNN while still allowing the individual behavioral patterns of the transformers to be distinguished. At the same time, dependencies between transformers are considered by the GNN architecture which can learn relationships between different transformers and thus take into account that power flows in an electricity network are not independent from each other. The effectiveness of the proposed method is demonstrated through evaluation on two real-world data sets provided by two of four German Transmission System Operators, comprising large portions of the operated German transmission grid. The results show that the proposed Multi-Task Graph Neural Network is a suitable representation learner for electricity networks with a clear advantage provided by the preceding embedding layer. It is able to capture interconnections between correlated transformers and indeed improves the performance in power flow prediction compared to standard Neural Networks. A sign test shows that the proposed model reduces the test RMSE on both data sets compared to the benchmark models significantly.
@article{beinert2023power, abstract = {The increasing share of renewable energy in the electricity grid and progressing changes in power consumption have led to fluctuating, and weather-dependent power flows. To ensure grid stability, grid operators rely on power forecasts which are crucial for grid calculations and planning. In this paper, a Multi-Task Learning approach is combined with a Graph Neural Network (GNN) to predict vertical power flows at transformers connecting high and extra-high voltage levels. The proposed method accounts for local differences in power flow characteristics by using an Embedding Multi-Task Learning approach. The use of a Bayesian embedding to capture the latent node characteristics allows to share the weights across all transformers in the subsequent node-invariant GNN while still allowing the individual behavioral patterns of the transformers to be distinguished. At the same time, dependencies between transformers are considered by the GNN architecture which can learn relationships between different transformers and thus take into account that power flows in an electricity network are not independent from each other. The effectiveness of the proposed method is demonstrated through evaluation on two real-world data sets provided by two of four German Transmission System Operators, comprising large portions of the operated German transmission grid. The results show that the proposed Multi-Task Graph Neural Network is a suitable representation learner for electricity networks with a clear advantage provided by the preceding embedding layer. It is able to capture interconnections between correlated transformers and indeed improves the performance in power flow prediction compared to standard Neural Networks. A sign test shows that the proposed model reduces the test RMSE on both data sets compared to the benchmark models significantly.}, author = {Beinert, Dominik and Holzhüter, Clara and Thomas, Josephine and Vogt, Stephan}, journal = {Energy and AI}, keywords = {itegpub}, number = 1, pages = 100262, publisher = {Elsevier}, title = {Power flow forecasts at transmission grid nodes using Graph Neural Networks}, volume = 14, year = 2023 }
%0 Journal Article %1 beinert2023power %A Beinert, Dominik %A Holzhüter, Clara %A Thomas, Josephine %A Vogt, Stephan %D 2023 %I Elsevier %J Energy and AI %N 1 %P 100262 %R 10.1016/j.egyai.2023.100262 %T Power flow forecasts at transmission grid nodes using Graph Neural Networks %U https://www.sciencedirect.com/science/article/pii/S2666546823000344?via%3Dihub %V 14 %X The increasing share of renewable energy in the electricity grid and progressing changes in power consumption have led to fluctuating, and weather-dependent power flows. To ensure grid stability, grid operators rely on power forecasts which are crucial for grid calculations and planning. In this paper, a Multi-Task Learning approach is combined with a Graph Neural Network (GNN) to predict vertical power flows at transformers connecting high and extra-high voltage levels. The proposed method accounts for local differences in power flow characteristics by using an Embedding Multi-Task Learning approach. The use of a Bayesian embedding to capture the latent node characteristics allows to share the weights across all transformers in the subsequent node-invariant GNN while still allowing the individual behavioral patterns of the transformers to be distinguished. At the same time, dependencies between transformers are considered by the GNN architecture which can learn relationships between different transformers and thus take into account that power flows in an electricity network are not independent from each other. The effectiveness of the proposed method is demonstrated through evaluation on two real-world data sets provided by two of four German Transmission System Operators, comprising large portions of the operated German transmission grid. The results show that the proposed Multi-Task Graph Neural Network is a suitable representation learner for electricity networks with a clear advantage provided by the preceding embedding layer. It is able to capture interconnections between correlated transformers and indeed improves the performance in power flow prediction compared to standard Neural Networks. A sign test shows that the proposed model reduces the test RMSE on both data sets compared to the benchmark models significantly.
Graph Neural Networks Designed for Different Graph Types: A Survey. Thomas, Josephine; Moallemy-Oureh, Alice; Beddar-Wiesing, Silvia; Holzhüter, Clara. In Transactions on Machine Learning Research. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based on graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field’s youth and the speed at which new models are developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give a detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph types and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.
@article{thomas2023graph, abstract = {Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based on graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field’s youth and the speed at which new models are developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give a detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph types and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.}, author = {Thomas, Josephine and Moallemy-Oureh, Alice and Beddar-Wiesing, Silvia and Holzhüter, Clara}, journal = {Transactions on Machine Learning Research}, keywords = {itegpub}, title = {Graph Neural Networks Designed for Different Graph Types: A Survey}, year = 2023 }
%0 Journal Article %1 thomas2023graph %A Thomas, Josephine %A Moallemy-Oureh, Alice %A Beddar-Wiesing, Silvia %A Holzhüter, Clara %D 2023 %J Transactions on Machine Learning Research %T Graph Neural Networks Designed for Different Graph Types: A Survey %U https://openreview.net/pdf?id=h4BYtZ79uy %X Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based on graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field’s youth and the speed at which new models are developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give a detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph types and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.

2022[ to top ]

Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs. Beddar-Wiesing, Silvia; D’Inverno, Giuseppe Alessio; Graziani, Caterina; Lachi, Veronica; Moallemy-Oureh, Alice; Scarselli, Franco; Thomas, Josephine. In arXiv e-prints, bl arXiv:2210.03990. 2022.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.
@article{beddarwiesing2022weisfeiler, abstract = {Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.}, author = {Beddar-Wiesing, Silvia and D'Inverno, Giuseppe Alessio and Graziani, Caterina and Lachi, Veronica and Moallemy-Oureh, Alice and Scarselli, Franco and Thomas, Josephine}, journal = {arXiv e-prints}, keywords = {itegpub}, pages = {arXiv:2210.03990}, title = {{W}eisfeiler-{L}ehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs}, year = 2022 }
%0 Journal Article %1 beddarwiesing2022weisfeiler %A Beddar-Wiesing, Silvia %A D'Inverno, Giuseppe Alessio %A Graziani, Caterina %A Lachi, Veronica %A Moallemy-Oureh, Alice %A Scarselli, Franco %A Thomas, Josephine %D 2022 %J arXiv e-prints %P arXiv:2210.03990 %T Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs %U https://arxiv.org/abs/2210.03990 %X Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.

2021[ to top ]

A Note on the Modeling Power of Different Graph Types. Thomas, Josephine M.; Beddar-Wiesing, Silvia; Moallemy-Oureh, Alice; Nather, Rüdiger. In arXiv e-prints, bl arXiv:2109.10708. 2021.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information. In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation. The expressivity relation quantifies how many properties a graph type can encode compared to another type. Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.
@article{thomas2021note, abstract = {Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information. In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation. The expressivity relation quantifies how many properties a graph type can encode compared to another type. Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.}, author = {Thomas, Josephine M. and Beddar-Wiesing, Silvia and Moallemy-Oureh, Alice and Nather, Rüdiger}, journal = {arXiv e-prints}, keywords = {itegpub}, pages = {arXiv:2109.10708}, title = {A Note on the Modeling Power of Different Graph Types}, year = 2021 }
%0 Journal Article %1 thomas2021note %A Thomas, Josephine M. %A Beddar-Wiesing, Silvia %A Moallemy-Oureh, Alice %A Nather, Rüdiger %D 2021 %J arXiv e-prints %P arXiv:2109.10708 %T A Note on the Modeling Power of Different Graph Types %U https://arxiv.org/abs/2109.10708 %X Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information. In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation. The expressivity relation quantifies how many properties a graph type can encode compared to another type. Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.

2017[ to top ]

Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Muscoloni, Alessandro; Thomas, Josephine Maria; Ciucci, Sara; Bianconi, Ginestra; Cannistraci, Carlo Vittorio. In Nature Communications, 8(1), bl 1615. Springer, 2017.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term "angular coalescence." Based on this phenomenon, we propose a class of algorithms that offers fast and accurate "coalescent embedding" in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science.
@article{muscoloni2017machine, abstract = {Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term "angular coalescence." Based on this phenomenon, we propose a class of algorithms that offers fast and accurate "coalescent embedding" in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science.}, author = {Muscoloni, Alessandro and Thomas, Josephine Maria and Ciucci, Sara and Bianconi, Ginestra and Cannistraci, Carlo Vittorio}, journal = {Nature Communications}, keywords = {not_ies}, number = 1, pages = 1615, publisher = {Springer}, title = {Machine learning meets complex networks via coalescent embedding in the hyperbolic space}, volume = 8, year = 2017 }
%0 Journal Article %1 muscoloni2017machine %A Muscoloni, Alessandro %A Thomas, Josephine Maria %A Ciucci, Sara %A Bianconi, Ginestra %A Cannistraci, Carlo Vittorio %D 2017 %I Springer %J Nature Communications %N 1 %P 1615 %R 10.1038/s41467-017-01825-5 %T Machine learning meets complex networks via coalescent embedding in the hyperbolic space %U https://doi.org/10.1038/s41467-017-01825-5 %V 8 %X Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term "angular coalescence." Based on this phenomenon, we propose a class of algorithms that offers fast and accurate "coalescent embedding" in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science.

2015[ to top ]

Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks. Daminelli, Simone; Thomas, Josephine Maria; Durán, Claudio; Cannistraci, Carlo Vittorio. In New Journal of Physics, 17(11), bl 113037. IOP Publishing, 2015.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Unveiling physical principles, building theories and suggesting physical models to predict bipartite links such as product-consumer connections in recommendation systems or drug–target interactions in molecular networks can provide priceless information to improve e-commerce or to accelerate pharmaceutical research. The prediction of nonobserved connections starting from those already present in the topology of a network is known as the link-prediction problem. It represents an important subject both in many-body interaction theory in physics and in new algorithms for applied tools in computer science. The rationale is that the existing connectivity structure of a network can suggest where new connections can appear with higher likelihood in an evolving network, or where nonobserved connections are missing in a partially known network. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.
@article{daminelli2015common, abstract = {Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Unveiling physical principles, building theories and suggesting physical models to predict bipartite links such as product-consumer connections in recommendation systems or drug–target interactions in molecular networks can provide priceless information to improve e-commerce or to accelerate pharmaceutical research. The prediction of nonobserved connections starting from those already present in the topology of a network is known as the link-prediction problem. It represents an important subject both in many-body interaction theory in physics and in new algorithms for applied tools in computer science. The rationale is that the existing connectivity structure of a network can suggest where new connections can appear with higher likelihood in an evolving network, or where nonobserved connections are missing in a partially known network. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.}, author = {Daminelli, Simone and Thomas, Josephine Maria and Durán, Claudio and Cannistraci, Carlo Vittorio}, journal = {New Journal of Physics}, keywords = {not_ies}, number = 11, pages = 113037, publisher = {IOP Publishing}, title = {Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks}, volume = 17, year = 2015 }
%0 Journal Article %1 daminelli2015common %A Daminelli, Simone %A Thomas, Josephine Maria %A Durán, Claudio %A Cannistraci, Carlo Vittorio %D 2015 %I IOP Publishing %J New Journal of Physics %N 11 %P 113037 %R 10.1088/1367-2630/17/11/113037 %T Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks %U https://iopscience.iop.org/article/10.1088/1367-2630/17/11/113037 %V 17 %X Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Unveiling physical principles, building theories and suggesting physical models to predict bipartite links such as product-consumer connections in recommendation systems or drug–target interactions in molecular networks can provide priceless information to improve e-commerce or to accelerate pharmaceutical research. The prediction of nonobserved connections starting from those already present in the topology of a network is known as the link-prediction problem. It represents an important subject both in many-body interaction theory in physics and in new algorithms for applied tools in computer science. The rationale is that the existing connectivity structure of a network can suggest where new connections can appear with higher likelihood in an evolving network, or where nonobserved connections are missing in a partially known network. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.