Vectorised Spreading Activation algorithm for centrality measurement
Spreading Activation is a family of graph-based algorithms widely used in areas such as information retrieval, epidemic models, and recommender systems. In this paper we introduce a novel Spreading Activation (SA) method that we call Vectorised Spreading Activation (VSA). VSA algorithms, like “tradi...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Mendel University Press
2011-01-01
|
| Series: | Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis |
| Subjects: | |
| Online Access: | https://acta.mendelu.cz/59/7/0469/ |
| _version_ | 1811277503133646848 |
|---|---|
| author | Alexander Troussov František Dařena Jan Žižka Denis Parra Peter Brusilovsky |
| author_facet | Alexander Troussov František Dařena Jan Žižka Denis Parra Peter Brusilovsky |
| author_sort | Alexander Troussov |
| collection | DOAJ |
| description | Spreading Activation is a family of graph-based algorithms widely used in areas such as information retrieval, epidemic models, and recommender systems. In this paper we introduce a novel Spreading Activation (SA) method that we call Vectorised Spreading Activation (VSA). VSA algorithms, like “traditional” SA algorithms, iteratively propagate the activation from the initially activated set of nodes to the other nodes in a network through outward links. The level of the node’s activation could be used as a centrality measurement in accordance with dynamic model-based view of centrality that focuses on the outcomes for nodes in a network where something is flowing from node to node across the edges. Representing the activation by vectors allows the use of the information about various dimensionalities of the flow and the dynamic of the flow. In this capacity, VSA algorithms can model multitude of complex multidimensional network flows. We present the results of numerical simulations on small synthetic social networks and multidimensional network models of folksonomies which show that the results of VSA propagation are more sensitive to the positions of the initial seed and to the community structure of the network than the results produced by traditional SA algorithms. We tentatively conclude that the VSA methods could be instrumental to develop scalable and computationally efficient algorithms which could achieve synergy between computation of centrality indexes with detection of community structures in networks. Based on our preliminary results and on improvements made over previous studies, we foresee advances and applications in the current state of the art of this family of algorithms and their applications to centrality measurement. |
| first_indexed | 2024-04-13T00:17:50Z |
| format | Article |
| id | doaj.art-59fa175f080645b0b132d529f74aa4c2 |
| institution | Directory Open Access Journal |
| issn | 1211-8516 2464-8310 |
| language | English |
| last_indexed | 2024-04-13T00:17:50Z |
| publishDate | 2011-01-01 |
| publisher | Mendel University Press |
| record_format | Article |
| series | Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis |
| spelling | doaj.art-59fa175f080645b0b132d529f74aa4c22022-12-22T03:10:53ZengMendel University PressActa Universitatis Agriculturae et Silviculturae Mendelianae Brunensis1211-85162464-83102011-01-0159746947610.11118/actaun201159070469Vectorised Spreading Activation algorithm for centrality measurementAlexander Troussov0František Dařena1Jan Žižka2Denis Parra3Peter Brusilovsky4BM Dublin Center for Advanced Studies, IBM IrelandÚstav informatiky / SoNet Research Center, Mendelova univerzita v Brně, Zemědělská 1, 613 00 BrnoÚstav informatiky / SoNet Research Center, Mendelova univerzita v Brně, Zemědělská 1, 613 00 BrnoUniversity of Pittsburgh, School of Information Sciences, University of Pittsburgh, 135 North Bellefield Ave., Pittsburgh, PA 15260, USAUniversity of Pittsburgh, School of Information Sciences, University of Pittsburgh, 135 North Bellefield Ave., Pittsburgh, PA 15260, USASpreading Activation is a family of graph-based algorithms widely used in areas such as information retrieval, epidemic models, and recommender systems. In this paper we introduce a novel Spreading Activation (SA) method that we call Vectorised Spreading Activation (VSA). VSA algorithms, like “traditional” SA algorithms, iteratively propagate the activation from the initially activated set of nodes to the other nodes in a network through outward links. The level of the node’s activation could be used as a centrality measurement in accordance with dynamic model-based view of centrality that focuses on the outcomes for nodes in a network where something is flowing from node to node across the edges. Representing the activation by vectors allows the use of the information about various dimensionalities of the flow and the dynamic of the flow. In this capacity, VSA algorithms can model multitude of complex multidimensional network flows. We present the results of numerical simulations on small synthetic social networks and multidimensional network models of folksonomies which show that the results of VSA propagation are more sensitive to the positions of the initial seed and to the community structure of the network than the results produced by traditional SA algorithms. We tentatively conclude that the VSA methods could be instrumental to develop scalable and computationally efficient algorithms which could achieve synergy between computation of centrality indexes with detection of community structures in networks. Based on our preliminary results and on improvements made over previous studies, we foresee advances and applications in the current state of the art of this family of algorithms and their applications to centrality measurement.https://acta.mendelu.cz/59/7/0469/centralitynetwork flowspreading activationgraph-based methodsrecommender systemsdata mining |
| spellingShingle | Alexander Troussov František Dařena Jan Žižka Denis Parra Peter Brusilovsky Vectorised Spreading Activation algorithm for centrality measurement Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis centrality network flow spreading activation graph-based methods recommender systems data mining |
| title | Vectorised Spreading Activation algorithm for centrality measurement |
| title_full | Vectorised Spreading Activation algorithm for centrality measurement |
| title_fullStr | Vectorised Spreading Activation algorithm for centrality measurement |
| title_full_unstemmed | Vectorised Spreading Activation algorithm for centrality measurement |
| title_short | Vectorised Spreading Activation algorithm for centrality measurement |
| title_sort | vectorised spreading activation algorithm for centrality measurement |
| topic | centrality network flow spreading activation graph-based methods recommender systems data mining |
| url | https://acta.mendelu.cz/59/7/0469/ |
| work_keys_str_mv | AT alexandertroussov vectorisedspreadingactivationalgorithmforcentralitymeasurement AT frantisekdarena vectorisedspreadingactivationalgorithmforcentralitymeasurement AT janzizka vectorisedspreadingactivationalgorithmforcentralitymeasurement AT denisparra vectorisedspreadingactivationalgorithmforcentralitymeasurement AT peterbrusilovsky vectorisedspreadingactivationalgorithmforcentralitymeasurement |