Graphs are ubiquitous in nature and can therefore serve as models for many practical but also
eoretical problems. For this purpose, they can be defined as many different types which
itably reflect the individual contexts of the represented problem. To address cutting-edge
oblems based on graph data, the research field of Graph Neural Networks (GNNs) has
erged. Despite the field’s youth and the speed at which new models are developed, many
cent surveys have been published to keep track of them. Nevertheless, it has not yet
en gathered which GNN can process what kind of graph types. In this survey, we give a
tailed overview of already existing GNNs and, unlike previous surveys, categorize them
cording to their ability to handle different graph types and properties. We consider GNNs
erating on static and dynamic graphs of different structural constitutions, with or without
de or edge attributes. Moreover, we distinguish between GNN models for discrete-time or
ntinuous-time dynamic graphs and group the models according to their architecture. We
nd that there are still graph types that are not or only rarely covered by existing GNN
dels. We point out where models are missing and give potential reasons for their absence.

@article{thomas2023graph, author = {Thomas, Josephine and Moallemy-Oureh, Alice and Beddar-Wiesing, Silvia and Holzhüter, Clara}, title = {Graph Neural Networks Designed for Different Graph Types: A Survey}, journal = {Transactions on Machine Learning Research}, year = {2023}, url = {https://openreview.net/pdf?id=h4BYtZ79uy}, keywords = {imported, itegpub, isac-www, graph, graph_type, graph_neural_network}, abstract = {Graphs are ubiquitous in nature and can therefore serve as models for many practical but alsotheoretical problems. For this purpose, they can be defined as many different types whichsuitably reflect the individual contexts of the represented problem. To address cutting-edgeproblems based on graph data, the research field of Graph Neural Networks (GNNs) hasemerged. Despite the field’s youth and the speed at which new models are developed, manyrecent surveys have been published to keep track of them. Nevertheless, it has not yetbeen gathered which GNN can process what kind of graph types. In this survey, we give adetailed overview of already existing GNNs and, unlike previous surveys, categorize themaccording to their ability to handle different graph types and properties. We consider GNNsoperating on static and dynamic graphs of different structural constitutions, with or withoutnode or edge attributes. Moreover, we distinguish between GNN models for discrete-time orcontinuous-time dynamic graphs and group the models according to their architecture. Wefind that there are still graph types that are not or only rarely covered by existing GNNmodels. We point out where models are missing and give potential reasons for their absence.} }

%0 = article %A = Thomas, Josephine and Moallemy-Oureh, Alice and Beddar-Wiesing, Silvia and Holzhüter, Clara %D = 2023 %T = Graph Neural Networks Designed for Different Graph Types: A Survey %U = https://openreview.net/pdf?id=h4BYtZ79uy

@inproceedings{DBLP:conf/dsaa/KrompassNT14, author = {Krompass, Denis and Nickel, Maximilian and Tresp, Volker}, title = {Large-scale factorization of type-constrained multi-relational data}, booktitle = {International Conference on Data Science and Advanced Analytics, DSAA 2014, Shanghai, China, October 30 - November 1, 2014}, publisher = {IEEE}, year = {2014}, pages = {18--24}, url = {http://dx.doi.org/10.1109/DSAA.2014.7058046}, doi = {10.1109/DSAA.2014.7058046}, isbn = {978-1-4799-6991-3}, keywords = {graph, knowledge, learning, toread} }

%0 = inproceedings %A = Krompass, Denis and Nickel, Maximilian and Tresp, Volker %B = International Conference on Data Science and Advanced Analytics, DSAA 2014, Shanghai, China, October 30 - November 1, 2014 %D = 2014 %I = IEEE %T = Large-scale factorization of type-constrained multi-relational data %U = http://dx.doi.org/10.1109/DSAA.2014.7058046

Since the rise of collaborative tagging systems on the web, the tag recommendation task - suggesting suitable tags to users of such systems while they add resources to their collection - has been tackled. However, the (offline) evaluation of tag recommendation algorithms usually suffers from difficulties like the sparseness of the data or the cold start problem for new resources or users. Previous studies therefore often used so-called post-cores (specific subsets of the original datasets) for their experiments. In this paper, we conduct a large-scale experiment in which we analyze different tag recommendation algorithms on different cores of three real-world datasets. We show, that a recommender's performance depends on the particular core and explore correlations between performances on different cores.

@inproceedings{doerfel2013analysis, author = {Doerfel, Stephan and Jäschke, Robert}, title = {An analysis of tag-recommender evaluation procedures}, booktitle = {Proceedings of the 7th ACM conference on Recommender systems}, series = {RecSys '13}, publisher = {ACM}, address = {New York, NY, USA}, year = {2013}, pages = {343--346}, url = {https://www.kde.cs.uni-kassel.de/pub/pdf/doerfel2013analysis.pdf}, doi = {10.1145/2507157.2507222}, isbn = {978-1-4503-2409-0}, keywords = {2013, bibsonomy, bookmarking, collaborative, core, evaluation, folkrank, folksonomy, graph, iteg, itegpub, l3s, recommender, social, tagging}, abstract = {Since the rise of collaborative tagging systems on the web, the tag recommendation task -- suggesting suitable tags to users of such systems while they add resources to their collection -- has been tackled. However, the (offline) evaluation of tag recommendation algorithms usually suffers from difficulties like the sparseness of the data or the cold start problem for new resources or users. Previous studies therefore often used so-called post-cores (specific subsets of the original datasets) for their experiments. In this paper, we conduct a large-scale experiment in which we analyze different tag recommendation algorithms on different cores of three real-world datasets. We show, that a recommender's performance depends on the particular core and explore correlations between performances on different cores.} }

%0 = inproceedings %A = Doerfel, Stephan and Jäschke, Robert %B = Proceedings of the 7th ACM conference on Recommender systems %C = New York, NY, USA %D = 2013 %I = ACM %T = An analysis of tag-recommender evaluation procedures %U = https://www.kde.cs.uni-kassel.de/pub/pdf/doerfel2013analysis.pdf

Bildeten die Keimzellen des Internet noch kleine und einfach strukturierte Netze, so vergrößerten sich sowohl seine physikalischen als auch seine logischen Topologien später rasant. Wuchs einerseits das Netz aus Rechnern als Knoten und Verbindungsleitungen als Kanten immer weiter, so bedienten sich andererseits gleichzeitig immer mehr Anwendungen dieser Infrastruktur, um darüber ihrerseits immer größere und komplexere virtuelle Netze zu weben, z. B. das WWW oder soziale Online-Netze. Auf jeder Ebene dieser Hierarchie lassen sich die jeweiligen Netztopologien mithilfe von Graphen beschreiben und so mathematisch untersuchen. So ergeben sich interessante Einblicke in die Struktureigenschaften unterschiedlicher Graphentypen, die großen Einfluss auf die Leistungsfähigkeit des Internet haben. Hierzu werden charakteristische Eigenschaften und entsprechende Kenngrößen verschiedener Graphentypen betrachtet wie der Knotengrad, die Durchschnittsdistanz, die Variation der Kantendichte in unterschiedlichen Netzteilen und die topologische Robustheit als Widerstandsfähigkeit gegenüber Ausfällen und Angriffen. Es wird dabei Bezug genommen auf analytische, simulative und zahlreiche empirische Untersuchungen des Internets und hingewiesen auf Simulationsprogramme sowie Abbildungen von Internetgraphen im Internet.

@article{noKey, author = {Heidtmann, Klaus}, title = {Internet-Graphen}, journal = {Informatik-Spektrum}, publisher = {Springer Berlin Heidelberg}, year = {2013}, volume = {36}, number = {5}, pages = {440-448}, url = {http://dx.doi.org/10.1007/s00287-012-0654-z}, doi = {10.1007/s00287-012-0654-z}, issn = {0170-6012}, keywords = {Graph, Graphen, Informatik, Informatik-Spektrum, Internet, Spektrum, graphs}, abstract = {Bildeten die Keimzellen des Internet noch kleine und einfach strukturierte Netze, so vergrößerten sich sowohl seine physikalischen als auch seine logischen Topologien später rasant. Wuchs einerseits das Netz aus Rechnern als Knoten und Verbindungsleitungen als Kanten immer weiter, so bedienten sich andererseits gleichzeitig immer mehr Anwendungen dieser Infrastruktur, um darüber ihrerseits immer größere und komplexere virtuelle Netze zu weben, z. B. das WWW oder soziale Online-Netze. Auf jeder Ebene dieser Hierarchie lassen sich die jeweiligen Netztopologien mithilfe von Graphen beschreiben und so mathematisch untersuchen. So ergeben sich interessante Einblicke in die Struktureigenschaften unterschiedlicher Graphentypen, die großen Einfluss auf die Leistungsfähigkeit des Internet haben. Hierzu werden charakteristische Eigenschaften und entsprechende Kenngrößen verschiedener Graphentypen betrachtet wie der Knotengrad, die Durchschnittsdistanz, die Variation der Kantendichte in unterschiedlichen Netzteilen und die topologische Robustheit als Widerstandsfähigkeit gegenüber Ausfällen und Angriffen. Es wird dabei Bezug genommen auf analytische, simulative und zahlreiche empirische Untersuchungen des Internets und hingewiesen auf Simulationsprogramme sowie Abbildungen von Internetgraphen im Internet. } }

%0 = article %A = Heidtmann, Klaus %D = 2013 %I = Springer Berlin Heidelberg %T = Internet-Graphen %U = http://dx.doi.org/10.1007/s00287-012-0654-z

The information contained in social tagging systems is often modelled as a graph of connections between users, items and tags. Recommendation algorithms such as FolkRank, have the potential to leverage complex relationships in the data, corresponding to multiple hops in the graph. We present an in-depth analysis and evaluation of graph models for social tagging data and propose novel adaptations and extensions of FolkRank to improve tag recommendations. We highlight implicit assumptions made by the widely used folksonomy model, and propose an alternative and more accurate graph-representation of the data. Our extensions of FolkRank address the new item problem by incorporating content data into the algorithm, and significantly improve prediction results on unpruned datasets. Our adaptations address issues in the iterative weight spreading calculation that potentially hinder FolkRank's ability to leverage the deep graph as an information source. Moreover, we evaluate the benefit of considering each deeper level of the graph, and present important insights regarding the characteristics of social tagging data in general. Our results suggest that the base assumption made by conventional weight propagation methods, that closeness in the graph always implies a positive relationship, does not hold for the social tagging domain.

@article{landia2013deeper, author = {Landia, Nikolas and Doerfel, Stephan and Jäschke, Robert and Anand, Sarabjot Singh and Hotho, Andreas and Griffiths, Nathan}, title = {Deeper Into the Folksonomy Graph: FolkRank Adaptations and Extensions for Improved Tag Recommendations}, journal = {cs.IR}, year = {2013}, volume = {1310.1498}, url = {http://arxiv.org/abs/1310.1498}, keywords = {2013, bookmarking, collaborative, folkrank, folksonomy, graph, iteg, itegpub, l3s, recommender, social, tagging}, abstract = {The information contained in social tagging systems is often modelled as a graph of connections between users, items and tags. Recommendation algorithms such as FolkRank, have the potential to leverage complex relationships in the data, corresponding to multiple hops in the graph. We present an in-depth analysis and evaluation of graph models for social tagging data and propose novel adaptations and extensions of FolkRank to improve tag recommendations. We highlight implicit assumptions made by the widely used folksonomy model, and propose an alternative and more accurate graph-representation of the data. Our extensions of FolkRank address the new item problem by incorporating content data into the algorithm, and significantly improve prediction results on unpruned datasets. Our adaptations address issues in the iterative weight spreading calculation that potentially hinder FolkRank's ability to leverage the deep graph as an information source. Moreover, we evaluate the benefit of considering each deeper level of the graph, and present important insights regarding the characteristics of social tagging data in general. Our results suggest that the base assumption made by conventional weight propagation methods, that closeness in the graph always implies a positive relationship, does not hold for the social tagging domain.} }

%0 = article %A = Landia, Nikolas and Doerfel, Stephan and Jäschke, Robert and Anand, Sarabjot Singh and Hotho, Andreas and Griffiths, Nathan %D = 2013 %T = Deeper Into the Folksonomy Graph: FolkRank Adaptations and Extensions for Improved Tag Recommendations %U = http://arxiv.org/abs/1310.1498

The information contained in social tagging systems is often modelled as a graph of connections between users, items and tags. Recommendation algorithms such as FolkRank, have the potential to leverage complex relationships in the data, corresponding to multiple hops in the graph. We present an in-depth analysis and evaluation of graph models for social tagging data and propose novel adaptations and extensions of FolkRank to improve tag recommendations. We highlight implicit assumptions made by the widely used folksonomy model, and propose an alternative and more accurate graph-representation of the data. Our extensions of FolkRank address the new item problem by incorporating content data into the algorithm, and significantly improve prediction results on unpruned datasets. Our adaptations address issues in the iterative weight spreading calculation that potentially hinder FolkRank's ability to leverage the deep graph as an information source. Moreover, we evaluate the benefit of considering each deeper level of the graph, and present important insights regarding the characteristics of social tagging data in general. Our results suggest that the base assumption made by conventional weight propagation methods, that closeness in the graph always implies a positive relationship, does not hold for the social tagging domain.

@article{landia2013deeper, author = {Landia, Nikolas and Doerfel, Stephan and Jäschke, Robert and Anand, Sarabjot Singh and Hotho, Andreas and Griffiths, Nathan}, title = {Deeper Into the Folksonomy Graph: FolkRank Adaptations and Extensions for Improved Tag Recommendations}, journal = {cs.IR}, year = {2013}, volume = {1310.1498}, url = {http://arxiv.org/abs/1310.1498}, keywords = {2013, bookmarking, collaborative, folkrank, folksonomy, graph, myown}, abstract = {The information contained in social tagging systems is often modelled as a graph of connections between users, items and tags. Recommendation algorithms such as FolkRank, have the potential to leverage complex relationships in the data, corresponding to multiple hops in the graph. We present an in-depth analysis and evaluation of graph models for social tagging data and propose novel adaptations and extensions of FolkRank to improve tag recommendations. We highlight implicit assumptions made by the widely used folksonomy model, and propose an alternative and more accurate graph-representation of the data. Our extensions of FolkRank address the new item problem by incorporating content data into the algorithm, and significantly improve prediction results on unpruned datasets. Our adaptations address issues in the iterative weight spreading calculation that potentially hinder FolkRank's ability to leverage the deep graph as an information source. Moreover, we evaluate the benefit of considering each deeper level of the graph, and present important insights regarding the characteristics of social tagging data in general. Our results suggest that the base assumption made by conventional weight propagation methods, that closeness in the graph always implies a positive relationship, does not hold for the social tagging domain.} }

%0 = article %A = Landia, Nikolas and Doerfel, Stephan and Jäschke, Robert and Anand, Sarabjot Singh and Hotho, Andreas and Griffiths, Nathan %D = 2013 %T = Deeper Into the Folksonomy Graph: FolkRank Adaptations and Extensions for Improved Tag Recommendations %U = http://arxiv.org/abs/1310.1498

The information contained in social tagging systems is often modelled as a graph of connections between users, items and tags. Recommendation algorithms such as FolkRank, have the potential to leverage complex relationships in the data, corresponding to multiple hops in the graph. We present an in-depth analysis and evaluation of graph models for social tagging data and propose novel adaptations and extensions of FolkRank to improve tag recommendations. We highlight implicit assumptions made by the widely used folksonomy model, and propose an alternative and more accurate graph-representation of the data. Our extensions of FolkRank address the new item problem by incorporating content data into the algorithm, and significantly improve prediction results on unpruned datasets. Our adaptations address issues in the iterative weight spreading calculation that potentially hinder FolkRank's ability to leverage the deep graph as an information source. Moreover, we evaluate the benefit of considering each deeper level of the graph, and present important insights regarding the characteristics of social tagging data in general. Our results suggest that the base assumption made by conventional weight propagation methods, that closeness in the graph always implies a positive relationship, does not hold for the social tagging domain.

@article{landia2013deeper, author = {Landia, Nikolas and Doerfel, Stephan and Jäschke, Robert and Anand, Sarabjot Singh and Hotho, Andreas and Griffiths, Nathan}, title = {Deeper Into the Folksonomy Graph: FolkRank Adaptations and Extensions for Improved Tag Recommendations}, journal = {cs.IR}, year = {2013}, volume = {1310.1498}, url = {http://arxiv.org/abs/1310.1498}, keywords = {2013, bookmarking, collaborative, folkrank, folksonomy, graph, myown, recommender, social, tagging}, abstract = {The information contained in social tagging systems is often modelled as a graph of connections between users, items and tags. Recommendation algorithms such as FolkRank, have the potential to leverage complex relationships in the data, corresponding to multiple hops in the graph. We present an in-depth analysis and evaluation of graph models for social tagging data and propose novel adaptations and extensions of FolkRank to improve tag recommendations. We highlight implicit assumptions made by the widely used folksonomy model, and propose an alternative and more accurate graph-representation of the data. Our extensions of FolkRank address the new item problem by incorporating content data into the algorithm, and significantly improve prediction results on unpruned datasets. Our adaptations address issues in the iterative weight spreading calculation that potentially hinder FolkRank's ability to leverage the deep graph as an information source. Moreover, we evaluate the benefit of considering each deeper level of the graph, and present important insights regarding the characteristics of social tagging data in general. Our results suggest that the base assumption made by conventional weight propagation methods, that closeness in the graph always implies a positive relationship, does not hold for the social tagging domain.} }

%0 = article %A = Landia, Nikolas and Doerfel, Stephan and Jäschke, Robert and Anand, Sarabjot Singh and Hotho, Andreas and Griffiths, Nathan %D = 2013 %T = Deeper Into the Folksonomy Graph: FolkRank Adaptations and Extensions for Improved Tag Recommendations %U = http://arxiv.org/abs/1310.1498

@article{liu2012fulltext, author = {Liu, Xiaozhong and Zhang, Jinsong and Guo, Chun}, title = {Full-Text Citation Analysis: A New Method to Enhance Scholarly Network}, journal = {Journal of the American Society for Information Science and Technology}, year = {2012}, url = {http://discern.uits.iu.edu:8790/publication/Full%20text%20citation.pdf}, keywords = {analysis, citation, classification, graph, pagerank, ranking, scientometrics, sota} }

%0 = article %A = Liu, Xiaozhong and Zhang, Jinsong and Guo, Chun %D = 2012 %T = Full-Text Citation Analysis: A New Method to Enhance Scholarly Network %U = http://discern.uits.iu.edu:8790/publication/Full%20text%20citation.pdf

@article{liu2012fulltext, author = {Liu, Xiaozhong and Zhang, Jinsong and Guo, Chun}, title = {Full-Text Citation Analysis: A New Method to Enhance Scholarly Network}, journal = {Journal of the American Society for Information Science and Technology}, year = {2012}, url = {http://discern.uits.iu.edu:8790/publication/Full%20text%20citation.pdf}, keywords = {analysis, citation, classification, graph, pagerank, ranking, scientometrics, sota, topic} }

%0 = article %A = Liu, Xiaozhong and Zhang, Jinsong and Guo, Chun %D = 2012 %T = Full-Text Citation Analysis: A New Method to Enhance Scholarly Network %U = http://discern.uits.iu.edu:8790/publication/Full%20text%20citation.pdf

The richness of the (Semantic) Web lies in its ability to link related resources as well as data across the Web. However, while relations within particular datasets are often well defined, links between disparate datasets and corpora of Web resources are rare. The increasingly widespread use of cross-domain reference datasets, such as Freebase and DBpedia for annotating and enriching datasets as well as document corpora, opens up opportunities to exploit their inherent semantics to uncover semantic relationships between disparate resources. In this paper, we present an approach to uncover relationships between disparate entities by analyzing the graphs of used reference datasets. We adapt a relationship assessment methodology from social network theory to measure the connectivity between entities in reference datasets and exploit these measures to identify correlated Web resources. Finally, we present an evaluation of our approach using the publicly available datasets Bibsonomy and USAToday.

@inproceedings{pereiranunes2012entities, author = {Pereira Nunes, Bernardo and Kawase, Ricardo and Dietze, Stefan and Taibi, Davide and Casanova, Marco Antonio and Nejdl, Wolfgang}, title = {Can Entities be Friends?}, editor = {Rizzo, Giuseppe and Mendes, Pablo and Charton, Eric and Hellmann, Sebastian and Kalyanpur, Aditya}, booktitle = {Proceedings of the Web of Linked Entities Workshop in conjuction with the 11th International Semantic Web Conference}, series = {CEUR-WS.org}, year = {2012}, volume = {906}, pages = {45--57}, url = {http://ceur-ws.org/Vol-906/paper6.pdf}, keywords = {data, detection, entity, graph, linked, relation, web}, abstract = {The richness of the (Semantic) Web lies in its ability to link related resources as well as data across the Web. However, while relations within particular datasets are often well defined, links between disparate datasets and corpora of Web resources are rare. The increasingly widespread use of cross-domain reference datasets, such as Freebase and DBpedia for annotating and enriching datasets as well as document corpora, opens up opportunities to exploit their inherent semantics to uncover semantic relationships between disparate resources. In this paper, we present an approach to uncover relationships between disparate entities by analyzing the graphs of used reference datasets. We adapt a relationship assessment methodology from social network theory to measure the connectivity between entities in reference datasets and exploit these measures to identify correlated Web resources. Finally, we present an evaluation of our approach using the publicly available datasets Bibsonomy and USAToday. } }

%0 = inproceedings %A = Pereira Nunes, Bernardo and Kawase, Ricardo and Dietze, Stefan and Taibi, Davide and Casanova, Marco Antonio and Nejdl, Wolfgang %B = Proceedings of the Web of Linked Entities Workshop in conjuction with the 11th International Semantic Web Conference %D = 2012 %T = Can Entities be Friends? %U = http://ceur-ws.org/Vol-906/paper6.pdf

The richness of the (Semantic) Web lies in its ability to link related resources as well as data across the Web. However, while relations within particular datasets are often well defined, links between disparate datasets and corpora of Web resources are rare. The increasingly widespread use of cross-domain reference datasets, such as Freebase and DBpedia for annotating and enriching datasets as well as document corpora, opens up opportunities to exploit their inherent semantics to uncover semantic relationships between disparate resources. In this paper, we present an approach to uncover relationships between disparate entities by analyzing the graphs of used reference datasets. We adapt a relationship assessment methodology from social network theory to measure the connectivity between entities in reference datasets and exploit these measures to identify correlated Web resources. Finally, we present an evaluation of our approach using the publicly available datasets Bibsonomy and USAToday.

@inproceedings{pereiranunes2012entities, author = {Pereira Nunes, Bernardo and Kawase, Ricardo and Dietze, Stefan and Taibi, Davide and Casanova, Marco Antonio and Nejdl, Wolfgang}, title = {Can Entities be Friends?}, editor = {Rizzo, Giuseppe and Mendes, Pablo and Charton, Eric and Hellmann, Sebastian and Kalyanpur, Aditya}, booktitle = {Proceedings of the Web of Linked Entities Workshop in conjuction with the 11th International Semantic Web Conference}, series = {CEUR-WS.org}, year = {2012}, volume = {906}, pages = {45--57}, url = {http://ceur-ws.org/Vol-906/paper6.pdf}, keywords = {data, detection, entity, graph, linked, relation, web}, abstract = {The richness of the (Semantic) Web lies in its ability to link related resources as well as data across the Web. However, while relations within particular datasets are often well defined, links between disparate datasets and corpora of Web resources are rare. The increasingly widespread use of cross-domain reference datasets, such as Freebase and DBpedia for annotating and enriching datasets as well as document corpora, opens up opportunities to exploit their inherent semantics to uncover semantic relationships between disparate resources. In this paper, we present an approach to uncover relationships between disparate entities by analyzing the graphs of used reference datasets. We adapt a relationship assessment methodology from social network theory to measure the connectivity between entities in reference datasets and exploit these measures to identify correlated Web resources. Finally, we present an evaluation of our approach using the publicly available datasets Bibsonomy and USAToday. } }

%0 = inproceedings %A = Pereira Nunes, Bernardo and Kawase, Ricardo and Dietze, Stefan and Taibi, Davide and Casanova, Marco Antonio and Nejdl, Wolfgang %B = Proceedings of the Web of Linked Entities Workshop in conjuction with the 11th International Semantic Web Conference %D = 2012 %T = Can Entities be Friends? %U = http://ceur-ws.org/Vol-906/paper6.pdf

The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on “ k -cores”, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity $$O(m)$$, where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k -core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in $$O(motn))$$ time, where n is the number of vertices and Δ is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.

@article{batagelj2011algorithms, author = {Batagelj, Vladimir and Zaveršnik, Matjaž}, title = {Fast algorithms for determining (generalized) core groups in social networks}, journal = {Advances in Data Analysis and Classification}, publisher = {Springer}, address = {Berlin / Heidelberg}, year = {2011}, volume = {5}, number = {2}, pages = {129-145}, url = {http://dx.doi.org/10.1007/s11634-010-0079-y}, doi = {10.1007/s11634-010-0079-y}, issn = {1862-5347}, keywords = {core, graph}, abstract = {The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on “ k -cores”, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity $$O(m)$$, where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k -core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in $$O(motn))$$ time, where n is the number of vertices and Δ is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.} }

%0 = article %A = Batagelj, Vladimir and Zaveršnik, Matjaž %C = Berlin / Heidelberg %D = 2011 %I = Springer %T = Fast algorithms for determining (generalized) core groups in social networks %U = http://dx.doi.org/10.1007/s11634-010-0079-y

We study the structure of the social graph of active Facebook users, the
rgest social network ever analyzed. We compute numerous features of the graph
cluding the number of users and friendships, the degree distribution, path
ngths, clustering, and mixing patterns. Our results center around three main
servations. First, we characterize the global structure of the graph,
termining that the social network is nearly fully connected, with 99.91% of
dividuals belonging to a single large connected component, and we confirm the
ix degrees of separation" phenomenon on a global scale. Second, by studying
e average local clustering coefficient and degeneracy of graph neighborhoods,
show that while the Facebook graph as a whole is clearly sparse, the graph
ighborhoods of users contain surprisingly dense structure. Third, we
aracterize the assortativity patterns present in the graph by studying the
sic demographic and network properties of users. We observe clear degree
sortativity and characterize the extent to which "your friends have more
iends than you". Furthermore, we observe a strong effect of age on friendship
eferences as well as a globally modular community structure driven by
tionality, but we do not find any strong gender homophily. We compare our
sults with those from smaller social networks and find mostly, but not
tirely, agreement on common structural network characteristics.

@misc{ugander2011anatomy, author = {Ugander, Johan and Karrer, Brian and Backstrom, Lars and Marlow, Cameron}, title = {The Anatomy of the Facebook Social Graph}, year = {2011}, note = {cite arxiv:1111.4503Comment: 17 pages, 9 figures, 1 table}, url = {http://arxiv.org/abs/1111.4503}, keywords = {facebook, graph, network, social}, abstract = {We study the structure of the social graph of active Facebook users, thelargest social network ever analyzed. We compute numerous features of the graphincluding the number of users and friendships, the degree distribution, pathlengths, clustering, and mixing patterns. Our results center around three mainobservations. First, we characterize the global structure of the graph,determining that the social network is nearly fully connected, with 99.91% ofindividuals belonging to a single large connected component, and we confirm the"six degrees of separation" phenomenon on a global scale. Second, by studyingthe average local clustering coefficient and degeneracy of graph neighborhoods,we show that while the Facebook graph as a whole is clearly sparse, the graphneighborhoods of users contain surprisingly dense structure. Third, wecharacterize the assortativity patterns present in the graph by studying thebasic demographic and network properties of users. We observe clear degreeassortativity and characterize the extent to which "your friends have morefriends than you". Furthermore, we observe a strong effect of age on friendshippreferences as well as a globally modular community structure driven bynationality, but we do not find any strong gender homophily. We compare ourresults with those from smaller social networks and find mostly, but notentirely, agreement on common structural network characteristics.} }

%0 = misc %A = Ugander, Johan and Karrer, Brian and Backstrom, Lars and Marlow, Cameron %B = } %C = %D = 2011 %I = %T = The Anatomy of the Facebook Social Graph} %U = http://arxiv.org/abs/1111.4503

The modeling of realistic networks is of great importance for modern complex systems research. Previous procedures typically model the natural growth of networks by means of iteratively adding nodes, geometric positioning information, a definition of link connectivity based on the preference for nearest neighbors or already highly connected nodes, or combine several of these approaches. Our novel model is based on the well-know concept of k-cores, originally introduced in social network analysis. Recent studies exposed the significant k-core structure of several real world systems, e.g. the AS network of the Internet. We present a simple and efficient method for generating networks which strictly adhere to the characteristics of a given k-core structure, called core fingerprint. We show-case our algorithm in a comparative evaluation with two well-known AS network generators.

@inproceedings{baur2007generating, author = {Baur, Michael and Gaertler, Marco and Görke, Robert and Krug, Marcus and Wagner, Dorothea}, title = {Generating Graphs with Predefined k-Core Structure}, booktitle = {Proceedings of the European Conference of Complex Systems}, year = {2007}, url = {http://i11www.ira.uka.de/extra/publications/bggkw-ggpcs-07.pdf}, keywords = {analysis, core, generator, graph, structure}, abstract = {The modeling of realistic networks is of great importance for modern complex systems research. Previous procedures typically model the natural growth of networks by means of iteratively adding nodes, geometric positioning information, a definition of link connectivity based on the preference for nearest neighbors or already highly connected nodes, or combine several of these approaches. Our novel model is based on the well-know concept of k-cores, originally introduced in social network analysis. Recent studies exposed the significant k-core structure of several real world systems, e.g. the AS network of the Internet. We present a simple and efficient method for generating networks which strictly adhere to the characteristics of a given k-core structure, called core fingerprint. We show-case our algorithm in a comparative evaluation with two well-known AS network generators. } }

%0 = inproceedings %A = Baur, Michael and Gaertler, Marco and Görke, Robert and Krug, Marcus and Wagner, Dorothea %B = Proceedings of the European Conference of Complex Systems %D = 2007 %T = Generating Graphs with Predefined k-Core Structure %U = http://i11www.ira.uka.de/extra/publications/bggkw-ggpcs-07.pdf

In this paper, we discuss two graphs in Wikipedia (i) the article graph, and (ii) the category graph. We perform a graph-theoretic analysis of the category graph, and show that it is a scale-free, small world graph like other well-known lexical semantic networks. We substantiate our findings by transferring semantic relatedness algorithms defined on WordNet to the Wikipedia category graph. To assess the usefulness of the category graph as an NLP resource, we analyze its coverage and the performance of the transferred semantic relatedness algorithms.

@inproceedings{zesch2007analysis, author = {Zesch, Torsten and Gurevych, Iryna}, title = {Analysis of the Wikipedia Category Graph for NLP Applications}, booktitle = {Proceedings of the TextGraphs-2 Workshop (NAACL-HLT)}, publisher = {Association for Computational Linguistics}, address = {Rochester}, year = {2007}, pages = {1--8}, url = {http://acl.ldc.upenn.edu/W/W07/W07-02.pdf#page=11}, keywords = {analysis, category, graph, language, natural, network, nlp, processing, wikipedia}, abstract = {In this paper, we discuss two graphs in Wikipedia (i) the article graph, and (ii) the category graph. We perform a graph-theoretic analysis of the category graph, and show that it is a scale-free, small world graph like other well-known lexical semantic networks. We substantiate our findings by transferring semantic relatedness algorithms defined on WordNet to the Wikipedia category graph. To assess the usefulness of the category graph as an NLP resource, we analyze its coverage and the performance of the transferred semantic relatedness algorithms. } }

%0 = inproceedings %A = Zesch, Torsten and Gurevych, Iryna %B = Proceedings of the TextGraphs-2 Workshop (NAACL-HLT) %C = Rochester %D = 2007 %I = Association for Computational Linguistics %T = Analysis of the Wikipedia Category Graph for NLP Applications %U = http://acl.ldc.upenn.edu/W/W07/W07-02.pdf#page=11

@book{diestel2006graphentheorie, author = {Diestel, Reinhard}, title = {Graph Theory}, publisher = {Springer-Verlag Heidelberg, New York}, year = {2005}, pages = {I-XVI, 1-344}, edition = {3 (electronic edition)}, url = {http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf}, keywords = {book, density, diesel, graph, theory} }

%0 = book %A = Diestel, Reinhard %D = 2005 %I = Springer-Verlag Heidelberg, New York %T = Graph Theory %U = http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf

The structure of large networks can be revealed by partitioning them to
aller parts, which are easier to handle. One of such decompositions is based
$k$-cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$,
$ is the number of lines, algorithm for determining the cores decomposition
a given network is presented.

@misc{batagelj2003algorithm, author = {Batagelj, V. and Zaversnik, M.}, title = {An O(m) Algorithm for Cores Decomposition of Networks}, year = {2003}, note = {cite arxiv:cs/0310049}, url = {http://arxiv.org/abs/cs/0310049}, keywords = {core, graph, network}, abstract = {The structure of large networks can be revealed by partitioning them tosmaller parts, which are easier to handle. One of such decompositions is basedon $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$,$m$ is the number of lines, algorithm for determining the cores decompositionof a given network is presented.} }

%0 = misc %A = Batagelj, V. and Zaversnik, M. %B = } %C = %D = 2003 %I = %T = An O(m) Algorithm for Cores Decomposition of Networks} %U = http://arxiv.org/abs/cs/0310049

@book{janson2000theory, author = {Janson, Svante and Luczak, Tomasz and Rucinski, Andrzej}, title = {Theory of random graphs}, publisher = {John Wiley & Sons}, address = {New York; Chichester}, year = {2000}, url = {http://www.amazon.com/Random-Graphs-Svante-Janson/dp/0471175412}, isbn = {0471175412 9780471175414}, keywords = {density, graph, random} }

%0 = book %A = Janson, Svante and Luczak, Tomasz and Rucinski, Andrzej %C = New York; Chichester %D = 2000 %I = John Wiley & Sons %T = Theory of random graphs %U = http://www.amazon.com/Random-Graphs-Svante-Janson/dp/0471175412

The structure of large graphs can be revealed by partitioning graphs to smaller parts, which are easier to handle. In the paper we propose the use of core decomposition as an efficient approach for partitioning large graphs. On the selected subgraphs, computationally more intensive, clustering and blockmodeling can be used to analyze their internal structure. The approach is illustrated by an analysis of Snyder & Kick’s world trade graph.

@incollection{batagelj1999partitioning, author = {Batagelj, Vladimir and Mrvar, Andrej and Zaveršnik, Matjaž}, title = {Partitioning Approach to Visualization of Large Graphs}, editor = {Kratochvíyl, Jan}, booktitle = {Graph Drawing}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, address = {Berlin / Heidelberg}, year = {1999}, volume = {1731}, pages = {90-97}, url = {http://dx.doi.org/10.1007/3-540-46648-7_9}, doi = {10.1007/3-540-46648-7_9}, isbn = {978-3-540-66904-3}, keywords = {core, graph}, abstract = {The structure of large graphs can be revealed by partitioning graphs to smaller parts, which are easier to handle. In the paper we propose the use of core decomposition as an efficient approach for partitioning large graphs. On the selected subgraphs, computationally more intensive, clustering and blockmodeling can be used to analyze their internal structure. The approach is illustrated by an analysis of Snyder & Kick’s world trade graph.} }

%0 = incollection %A = Batagelj, Vladimir and Mrvar, Andrej and Zaveršnik, Matjaž %B = Graph Drawing %C = Berlin / Heidelberg %D = 1999 %I = Springer %T = Partitioning Approach to Visualization of Large Graphs %U = http://dx.doi.org/10.1007/3-540-46648-7_9

Social network researchers have long sought measures of network cohesion, Density has often been used for this purpose, despite its generally admitted deficiencies. An approach to network cohesion is proposed that is based on minimum degree and which produces a sequence of subgraphs of gradually increasing cohesion. The approach also associates with any network measures of local density which promise to be useful both in characterizing network structures and in comparing networks.

@article{seidman1983network, author = {Seidman, Stephen B.}, title = {Network structure and minimum degree}, journal = {Social Networks}, year = {1983}, volume = {5}, number = {3}, pages = {269 - 287}, url = {http://www.sciencedirect.com/science/article/pii/037887338390028X}, doi = {10.1016/0378-8733(83)90028-X}, issn = {0378-8733}, keywords = {core, graph, network}, abstract = {Social network researchers have long sought measures of network cohesion, Density has often been used for this purpose, despite its generally admitted deficiencies. An approach to network cohesion is proposed that is based on minimum degree and which produces a sequence of subgraphs of gradually increasing cohesion. The approach also associates with any network measures of local density which promise to be useful both in characterizing network structures and in comparing networks.} }

%0 = article %A = Seidman, Stephen B. %D = 1983 %T = Network structure and minimum degree %U = http://www.sciencedirect.com/science/article/pii/037887338390028X