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

Graph conductance queries, also known as personalized PageRank and related to random walks with restarts, were originally proposed to assign a hyperlink-based prestige score to Web pages. More general forms of such queries are also very useful for ranking in entity-relation (ER) graphs used to represent relational, XML and hypertext data. Evaluation of PageRank usually involves a global eigen computation. If the graph is even moderately large, interactive response times may not be possible. Recently, the need for interactive PageRank evaluation has increased. The graph may be fully known only when the query is submitted. Browsing actions of the user may change some inputs to the PageRank computation dynamically. In this paper, we describe a system that analyzes query workloads and the ER graph, invests in limited offline indexing, and exploits those indices to achieve essentially constant-time query processing, even as the graph size scales. Our techniques—data and query statistics collection, index selection and materialization, and query-time index exploitation—have parallels in the extensive relational query optimization literature, but is applied to supporting novel graph data repositories. We report on experiments with five temporal snapshots of the CiteSeer ER graph having 74–702 thousand entity nodes, 0.17–1.16 million word nodes, 0.29–3.26 million edges between entities, and 3.29–32.8 million edges between words and entities. We also used two million actual queries from CiteSeer’s logs. Queries run 3–4 orders of magnitude faster than whole-graph PageRank, the gap growing with graph size. Index size is smaller than a text index. Ranking accuracy is 94–98% with reference to whole-graph PageRank.

@article{springerlink:10.1007/s00778-010-0204-8, author = {Chakrabarti, Soumen and Pathak, Amit and Gupta, Manish}, title = {Index design and query processing for graph conductance search}, journal = {The VLDB Journal}, publisher = {Springer}, address = {Berlin / Heidelberg}, year = {2010}, pages = {1-26}, url = {http://dx.doi.org/10.1007/s00778-010-0204-8}, doi = {10.1007/s00778-010-0204-8}, issn = {1066-8888}, keywords = {design, graph, index, interactive, pagerank, processing, query, toRead, folkrank}, abstract = {Graph conductance queries, also known as personalized PageRank and related to random walks with restarts, were originally proposed to assign a hyperlink-based prestige score to Web pages. More general forms of such queries are also very useful for ranking in entity-relation (ER) graphs used to represent relational, XML and hypertext data. Evaluation of PageRank usually involves a global eigen computation. If the graph is even moderately large, interactive response times may not be possible. Recently, the need for interactive PageRank evaluation has increased. The graph may be fully known only when the query is submitted. Browsing actions of the user may change some inputs to the PageRank computation dynamically. In this paper, we describe a system that analyzes query workloads and the ER graph, invests in limited offline indexing, and exploits those indices to achieve essentially constant-time query processing, even as the graph size scales. Our techniques—data and query statistics collection, index selection and materialization, and query-time index exploitation—have parallels in the extensive relational query optimization literature, but is applied to supporting novel graph data repositories. We report on experiments with five temporal snapshots of the CiteSeer ER graph having 74–702 thousand entity nodes, 0.17–1.16 million word nodes, 0.29–3.26 million edges between entities, and 3.29–32.8 million edges between words and entities. We also used two million actual queries from CiteSeer’s logs. Queries run 3–4 orders of magnitude faster than whole-graph PageRank, the gap growing with graph size. Index size is smaller than a text index. Ranking accuracy is 94–98% with reference to whole-graph PageRank.} }

%0 = article %A = Chakrabarti, Soumen and Pathak, Amit and Gupta, Manish %C = Berlin / Heidelberg %D = 2010 %I = Springer %T = Index design and query processing for graph conductance search %U = http://dx.doi.org/10.1007/s00778-010-0204-8

@article{journals/corr/abs-1006-1260, author = {Isella, Lorenzo and Stehlé, Juliette and Barrat, Alain and Cattuto, Ciro and Pinton, Jean-François and den Broeck, Wouter Van}, title = {What's in a crowd? Analysis of face-to-face behavioral networks}, journal = {CoRR}, year = {2010}, volume = {abs/1006.1260}, note = {informal publication}, url = {http://dblp.uni-trier.de/db/journals/corr/corr1006.html#abs-1006-1260}, keywords = {analysis, contact, crowd, graph, network, rfid, social, to, venus} }

%0 = article %A = Isella, Lorenzo and Stehlé, Juliette and Barrat, Alain and Cattuto, Ciro and Pinton, Jean-François and den Broeck, Wouter Van %D = 2010 %T = What's in a crowd? Analysis of face-to-face behavioral networks %U = http://dblp.uni-trier.de/db/journals/corr/corr1006.html#abs-1006-1260

@inproceedings{mitzlaff2010visit, author = {Mitzlaff, Folke and Benz, Dominik and Stumme, Gerd and Hotho, Andreas}, title = {Visit me, click me, be my friend: An analysis of evidence networks of user relationships in Bibsonomy}, booktitle = {Proceedings of the 21st ACM conference on Hypertext and hypermedia}, address = {Toronto, Canada}, year = {2010}, note = {(to appear)}, url = {http://www.kde.cs.uni-kassel.de/pub/pdf/mitzlaff2010visit.pdf}, keywords = {2010, analysis, evidence_networks, graph, itegpub, myown, social_links, social_network, user_relationships} }

%0 = inproceedings %A = Mitzlaff, Folke and Benz, Dominik and Stumme, Gerd and Hotho, Andreas %B = Proceedings of the 21st ACM conference on Hypertext and hypermedia %C = Toronto, Canada %D = 2010 %T = Visit me, click me, be my friend: An analysis of evidence networks of user relationships in Bibsonomy %U = http://www.kde.cs.uni-kassel.de/pub/pdf/mitzlaff2010visit.pdf

@inproceedings{mitzlaff2010visit, author = {Mitzlaff, Folke and Benz, Dominik and Stumme, Gerd and Hotho, Andreas}, title = {Visit me, click me, be my friend: An analysis of evidence networks of user relationships in Bibsonomy}, booktitle = {Proceedings of the 21st ACM conference on Hypertext and hypermedia}, address = {Toronto, Canada}, year = {2010}, note = {(to appear)}, url = {http://www.kde.cs.uni-kassel.de/pub/pdf/mitzlaff2010visit.pdf}, keywords = {graph, social_links, social_network, myown, evidence_networks, 2010, analysis, user_relationships, itegpub} }

%0 = inproceedings %A = Mitzlaff, Folke and Benz, Dominik and Stumme, Gerd and Hotho, Andreas %B = Proceedings of the 21st ACM conference on Hypertext and hypermedia %C = Toronto, Canada %D = 2010 %T = Visit me, click me, be my friend: An analysis of evidence networks of user relationships in Bibsonomy %U = http://www.kde.cs.uni-kassel.de/pub/pdf/mitzlaff2010visit.pdf

@inproceedings{conf/pkdd/AkogluF09, author = {Akoglu, Leman and Faloutsos, Christos}, title = {RTG: A Recursive Realistic Graph Generator Using Random Typing.}, editor = {Buntine, Wray L. and Grobelnik, Marko and Mladenic, Dunja and Shawe-Taylor, John}, booktitle = {ECML/PKDD (1)}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, year = {2009}, volume = {5781}, pages = {13-28}, url = {http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-1.html#AkogluF09}, isbn = {978-3-642-04179-2}, keywords = {2009, ecml, generator, graph, law, pkdd, power, properties} }

%0 = inproceedings %A = Akoglu, Leman and Faloutsos, Christos %B = ECML/PKDD (1) %D = 2009 %I = Springer %T = RTG: A Recursive Realistic Graph Generator Using Random Typing. %U = http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-1.html#AkogluF09

@inproceedings{conf/pkdd/BerlingerioBBG09, author = {Berlingerio, Michele and Bonchi, Francesco and Bringmann, Björn and Gionis, Aristides}, title = {Mining Graph Evolution Rules.}, editor = {Buntine, Wray L. and Grobelnik, Marko and Mladenic, Dunja and Shawe-Taylor, John}, booktitle = {ECML/PKDD (1)}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, year = {2009}, volume = {5781}, pages = {115-130}, url = {http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-1.html#BerlingerioBBG09}, isbn = {978-3-642-04179-2}, keywords = {2009, ecml, evolution, generation, graph, pkdd, time} }

%0 = inproceedings %A = Berlingerio, Michele and Bonchi, Francesco and Bringmann, Björn and Gionis, Aristides %B = ECML/PKDD (1) %D = 2009 %I = Springer %T = Mining Graph Evolution Rules. %U = http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-1.html#BerlingerioBBG09

Bipartite ranking refers to the problem of learning a ranking function from a training set of positively and negatively labeled
amples. Applied to a set of unlabeled instances, a ranking function is expected to establish a total order in which positiveinstances precede negative ones. The performance of a ranking function is typically measured in terms of the AUC. In thispaper, we study the problem of multipartite ranking, an extension of bipartite ranking to the multi-class case. In this regard,we discuss extensions of the AUC metric which are suitable as evaluation criteria for multipartite rankings. Moreover, tolearn multipartite ranking functions, we propose methods on the basis of binary decomposition techniques that have previouslybeen used for multi-class and ordinal classification. We compare these methods both analytically and experimentally, not onlyagainst each other but also to existing methods applicable to the same problem.

@article{johannes2009binary, author = {Fürnkranz, Johannes and Hüllermeier, Eyke and Vanderlooy, Stijn}, title = {Binary Decomposition Methods for Multipartite Ranking}, journal = {Machine Learning and Knowledge Discovery in Databases}, year = {2009}, pages = {359--374}, url = {http://dx.doi.org/10.1007/978-3-642-04180-8_41}, keywords = {2009, ecml, graph, multipartite, pkdd, ranking}, abstract = {Bipartite ranking refers to the problem of learning a ranking function from a training set of positively and negatively labeled examples. Applied to a set of unlabeled instances, a ranking function is expected to establish a total order in which positiveinstances precede negative ones. The performance of a ranking function is typically measured in terms of the AUC. In thispaper, we study the problem of multipartite ranking, an extension of bipartite ranking to the multi-class case. In this regard,we discuss extensions of the AUC metric which are suitable as evaluation criteria for multipartite rankings. Moreover, tolearn multipartite ranking functions, we propose methods on the basis of binary decomposition techniques that have previouslybeen used for multi-class and ordinal classification. We compare these methods both analytically and experimentally, not onlyagainst each other but also to existing methods applicable to the same problem.} }

%0 = article %A = Fürnkranz, Johannes and Hüllermeier, Eyke and Vanderlooy, Stijn %D = 2009 %T = Binary Decomposition Methods for Multipartite Ranking %U = http://dx.doi.org/10.1007/978-3-642-04180-8_41

Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through dimensionality reduction techniques. However, these traditional methods often do not capture well the underlying structural information, clustering, and neighborhoods. In this paper, we describe GMap: a practical tool for visualizing relational data with geographic-like maps. We illustrate the effectiveness of this approach with examples from several domains All the maps referenced in this paper can be found in http://www.research.att.com/~yifanhu/GMap

@article{gansner2009drawing, author = {Gansner, Emden R. and Hu, Yifan and Kobourov, Stephen G.}, title = {GMap: Drawing Graphs as Maps}, journal = {cs.CG}, year = {2009}, volume = {arXiv:0907.2585v1}, url = {http://arxiv.org/abs/0907.2585}, keywords = {analysis, citation, drawing, gmap, graph, graphics, graphviz, network, sna, social, visualization}, abstract = {Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through dimensionality reduction techniques. However, these traditional methods often do not capture well the underlying structural information, clustering, and neighborhoods. In this paper, we describe GMap: a practical tool for visualizing relational data with geographic-like maps. We illustrate the effectiveness of this approach with examples from several domains All the maps referenced in this paper can be found in http://www.research.att.com/~yifanhu/GMap } }

%0 = article %A = Gansner, Emden R. and Hu, Yifan and Kobourov, Stephen G. %D = 2009 %T = GMap: Drawing Graphs as Maps %U = http://arxiv.org/abs/0907.2585

Heterogeneous networks play a key role in the evolution of communities and
e decisions individuals make. These networks link different types of
tities, for example, people and the events they attend. Network analysis
gorithms usually project such networks unto simple graphs composed of
tities of a single type. In the process, they conflate relations between
tities of different types and loose important structural information. We
velop a mathematical framework that can be used to compactly represent and
alyze heterogeneous networks that combine multiple entity and link types. We
neralize Bonacich centrality, which measures connectivity between nodes by
e number of paths between them, to heterogeneous networks and use this
asure to study network structure. Specifically, we extend the popular
dularity-maximization method for community detection to use this centrality
tric. We also rank nodes based on their connectivity to other nodes. One
vantage of this centrality metric is that it has a tunable parameter we can
e to set the length scale of interactions. By studying how rankings change
th this parameter allows us to identify important nodes in the network. We
ply the proposed method to analyze the structure of several heterogeneous
tworks. We show that exploiting additional sources of evidence corresponding
links between, as well as among, different entity types yields new insights
to network structure.

@misc{Ghosh2009, author = {Ghosh, Rumi and Lerman, Kristina}, title = {Structure of Heterogeneous Networks}, year = {2009}, note = {cite arxiv:0906.2212
}, url = {http://arxiv.org/abs/0906.2212}, keywords = {graph, graphs, heterogenous, measures, multi-mode, networks, sna}, abstract = { Heterogeneous networks play a key role in the evolution of communities andthe decisions individuals make. These networks link different types ofentities, for example, people and the events they attend. Network analysisalgorithms usually project such networks unto simple graphs composed ofentities of a single type. In the process, they conflate relations betweenentities of different types and loose important structural information. Wedevelop a mathematical framework that can be used to compactly represent andanalyze heterogeneous networks that combine multiple entity and link types. Wegeneralize Bonacich centrality, which measures connectivity between nodes bythe number of paths between them, to heterogeneous networks and use thismeasure to study network structure. Specifically, we extend the popularmodularity-maximization method for community detection to use this centralitymetric. We also rank nodes based on their connectivity to other nodes. Oneadvantage of this centrality metric is that it has a tunable parameter we canuse to set the length scale of interactions. By studying how rankings changewith this parameter allows us to identify important nodes in the network. Weapply the proposed method to analyze the structure of several heterogeneousnetworks. We show that exploiting additional sources of evidence correspondingto links between, as well as among, different entity types yields new insightsinto network structure.} }

%0 = misc %A = Ghosh, Rumi and Lerman, Kristina %B = } %C = %D = 2009 %I = %T = Structure of Heterogeneous Networks} %U = http://arxiv.org/abs/0906.2212

Collective classification refers to the classification of interlinked and relational objects described as nodes in a graph. The Iterative Classification Algorithm (ICA) is a simple, efficient and widely used method to solve this problem. It is representative of a family of methods for which inference proceeds as an iterative process: at each step, nodes of the graph are classified according to the current predicted labels of their neighbors. We show that learning in this class of models suffers from a training bias. We propose a new family of methods, called Simulated ICA, which helps reducing this training bias by simulating inference during learning. Several variants of the method are introduced. They are both simple, efficient and scale well. Experiments performed on a series of 7 datasets show that the proposed methods outperform representative state-of-the-art algorithms while keeping a low complexity.

@inproceedings{conf/pkdd/MaesPDG09, author = {Maes, Francis and Peters, Stéphane and Denoyer, Ludovic and Gallinari, Patrick}, title = {Simulated Iterative Classification A New Learning Procedure for Graph Labeling.}, editor = {Buntine, Wray L. and Grobelnik, Marko and Mladenic, Dunja and Shawe-Taylor, John}, booktitle = {ECML/PKDD (2)}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, year = {2009}, volume = {5782}, pages = {47-62}, url = {http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-2.html#MaesPDG09}, isbn = {978-3-642-04173-0}, keywords = {2009, classification, ecml, graph, iterative, label, labeling, multi, pkdd}, abstract = {Collective classification refers to the classification of interlinked and relational objects described as nodes in a graph. The Iterative Classification Algorithm (ICA) is a simple, efficient and widely used method to solve this problem. It is representative of a family of methods for which inference proceeds as an iterative process: at each step, nodes of the graph are classified according to the current predicted labels of their neighbors. We show that learning in this class of models suffers from a training bias. We propose a new family of methods, called Simulated ICA, which helps reducing this training bias by simulating inference during learning. Several variants of the method are introduced. They are both simple, efficient and scale well. Experiments performed on a series of 7 datasets show that the proposed methods outperform representative state-of-the-art algorithms while keeping a low complexity.} }

%0 = inproceedings %A = Maes, Francis and Peters, Stéphane and Denoyer, Ludovic and Gallinari, Patrick %B = ECML/PKDD (2) %D = 2009 %I = Springer %T = Simulated Iterative Classification A New Learning Procedure for Graph Labeling. %U = http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-2.html#MaesPDG09

Real-world relations are often represented as bipartite networks, such as paper-author networks and event-attendee networks. Extracting dense subnetworks (communities) from bipartite networks and evaluating their qualities are practically important research topics. As the attempts for evaluating divisions of bipartite networks, Guimera and Barber propose bipartite modularities. This paper discusses the properties of these bipartite modularities and proposes another bipartite modularity that allows one-to-many correspondence of communities of different vertex types. Preliminary experimental results for the bipartite modularities are also described.

@inproceedings{murata2009modularities, author = {Murata, Tsuyoshi}, title = {Modularities for Bipartite Networks}, booktitle = {HT '09: Proceedings of the Twentieth ACM Conference on Hypertext and Hypermedia}, publisher = {ACM}, address = {New York, NY, USA}, year = {2009}, keywords = {ht09, graph, bipartite}, abstract = {Real-world relations are often represented as bipartite networks, such as paper-author networks and event-attendee networks. Extracting dense subnetworks (communities) from bipartite networks and evaluating their qualities are practically important research topics. As the attempts for evaluating divisions of bipartite networks, Guimera and Barber propose bipartite modularities. This paper discusses the properties of these bipartite modularities and proposes another bipartite modularity that allows one-to-many correspondence of communities of different vertex types. Preliminary experimental results for the bipartite modularities are also described.} }

%0 = inproceedings %A = Murata, Tsuyoshi %B = HT '09: Proceedings of the Twentieth ACM Conference on Hypertext and Hypermedia %C = New York, NY, USA %D = 2009 %I = ACM %T = Modularities for Bipartite Networks

@phdthesis{butler2008eas, author = {Butler, S.K.}, title = {Eigenvalues and Structures of Graphs}, school = {University of California, San Diego}, year = {2008}, keywords = {graph, spectral, theory} }

%0 = phdthesis %A = Butler, S.K. %D = 2008 %T = Eigenvalues and Structures of Graphs

@article{filippone2008ska, author = {Filippone, M. and Camastra, F. and Masulli, F. and Rovetta, S.}, title = {A survey of kernel and spectral methods for clustering}, journal = {Pattern recognition}, publisher = {Elsevier}, year = {2008}, volume = {41}, number = {1}, pages = {176--190}, keywords = {community, detection, graph, kernel, spectral, survey, theory} }

%0 = article %A = Filippone, M. and Camastra, F. and Masulli, F. and Rovetta, S. %D = 2008 %I = Elsevier %T = A survey of kernel and spectral methods for clustering

I examine a random network model where nodes are categorized by type and linking probabilities can differ across types. I
ow that as homophily increases (so that the probability to link to other nodes of the same type increases and the probabilityof linking to nodes of some other types decreases) the average distance and diameter of the network are unchanged, while theaverage clustering in the network increases.

@article{matthew2008average, author = {Jackson, Matthew}, title = {Average Distance, Diameter, and Clustering in Social Networks with Homophily}, journal = {Internet and Network Economics}, year = {2008}, pages = {4--11}, url = {http://dx.doi.org/10.1007/978-3-540-92185-1_3}, keywords = {generator, graph, homophily, properties}, abstract = {I examine a random network model where nodes are categorized by type and linking probabilities can differ across types. I show that as homophily increases (so that the probability to link to other nodes of the same type increases and the probabilityof linking to nodes of some other types decreases) the average distance and diameter of the network are unchanged, while theaverage clustering in the network increases.} }

%0 = article %A = Jackson, Matthew %D = 2008 %T = Average Distance, Diameter, and Clustering in Social Networks with Homophily %U = http://dx.doi.org/10.1007/978-3-540-92185-1_3

Complex networks topologies present interesting and surprising properties,
ch as community structures, which can be exploited to optimize communication,
find new efficient and context-aware routing algorithms or simply to
derstand the dynamics and meaning of relationships among nodes. Complex
tworks are gaining more and more importance as a reference model and are a
werful interpretation tool for many different kinds of natural, biological
d social networks, where directed relationships and contextual belonging of
des to many different communities is a matter of fact. This paper starts from
e definition of modularity function, given by M. Newman to evaluate the
odness of network community decompositions, and extends it to the more
neral case of directed graphs with overlapping community structures.
teresting properties of the proposed extension are discussed, a method for
nding overlapping communities is proposed and results of its application to
nchmark case-studies are reported. We also propose a new dataset which could
used as a reference benchmark for overlapping community structures
entification.

@misc{Nicosia2008, author = {Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M.}, title = {Extending the definition of modularity to directed graphs with
overlapping communities}, year = {2008}, note = {cite arxiv:0801.1647
mment: 22 pages, 11 figures}, url = {http://arxiv.org/abs/0801.1647}, keywords = {COMMUNE, community, directed, graph, modularity, network, overlapping}, abstract = { Complex networks topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of modularity function, given by M. Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new dataset which could be used as a reference benchmark for overlapping community structures identification. } }

%0 = misc %A = Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M. %B = } %C = %D = 2008 %I = %T = Extending the definition of modularity to directed graphs with
overlapping communities} %U = http://arxiv.org/abs/0801.1647

@inproceedings{1454017, author = {Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis}, title = {Tag recommendations based on tensor dimensionality reduction}, booktitle = {RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems}, publisher = {ACM}, address = {New York, NY, USA}, year = {2008}, pages = {43--50}, url = {http://portal.acm.org/citation.cfm?id=1454017}, doi = {http://doi.acm.org/10.1145/1454008.1454017}, isbn = {978-1-60558-093-7}, keywords = {community, detection, graph, recommender, spectral, tag, theory} }

%0 = inproceedings %A = Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis %B = RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems %C = New York, NY, USA %D = 2008 %I = ACM %T = Tag recommendations based on tensor dimensionality reduction %U = http://portal.acm.org/citation.cfm?id=1454017

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

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.

@incollection{springerlink:10.1007/978-3-540-74839-7_12, author = {Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea}, title = {On Finding Graph Clusterings with Maximum Modularity}, editor = {Brandstädt, Andreas and Kratsch, Dieter and Müller, Haiko}, booktitle = {Graph-Theoretic Concepts in Computer Science}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, address = {Berlin / Heidelberg}, year = {2007}, volume = {4769}, pages = {121-132}, url = {http://dx.doi.org/10.1007/978-3-540-74839-7_12}, doi = {10.1007/978-3-540-74839-7_12}, isbn = {978-3-540-74838-0}, keywords = {clustering, graph, modularity, theory}, abstract = {Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.} }

%0 = incollection %A = Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea %B = Graph-Theoretic Concepts in Computer Science %C = Berlin / Heidelberg %D = 2007 %I = Springer %T = On Finding Graph Clusterings with Maximum Modularity %U = http://dx.doi.org/10.1007/978-3-540-74839-7_12

@article{1288832, author = {Luxburg, Ulrike}, title = {A tutorial on spectral clustering}, journal = {Statistics and Computing}, publisher = {Kluwer Academic Publishers}, address = {Hingham, MA, USA}, year = {2007}, volume = {17}, number = {4}, pages = {395--416}, url = {http://portal.acm.org/citation.cfm?id=1288832}, doi = {http://dx.doi.org/10.1007/s11222-007-9033-z}, issn = {0960-3174}, keywords = {community, detection, graph, spectral, theory} }

%0 = article %A = Luxburg, Ulrike %C = Hingham, MA, USA %D = 2007 %I = Kluwer Academic Publishers %T = A tutorial on spectral clustering %U = http://portal.acm.org/citation.cfm?id=1288832

@article{schaeffer2007graph, author = {Schaeffer, S.E.}, title = {Graph clustering}, journal = {Computer Science Review}, publisher = {Elsevier}, year = {2007}, volume = {1}, number = {1}, pages = {27--64}, url = {http://scholar.google.de/scholar.bib?q=info:-vQhplU2EFYJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {clustering, community, detection, graph} }

%0 = article %A = Schaeffer, S.E. %D = 2007 %I = Elsevier %T = Graph clustering %U = http://scholar.google.de/scholar.bib?q=info:-vQhplU2EFYJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.

@article{4389477, author = {Spielman, D.A.}, title = {Spectral Graph Theory and its Applications}, journal = {Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on}, year = {2007}, pages = {29-38}, doi = {10.1109/FOCS.2007.56}, issn = {0272-5428}, keywords = {graph, spectral, theory}, abstract = {Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.} }

%0 = article %A = Spielman, D.A. %D = 2007 %T = Spectral Graph Theory and its Applications

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

@unpublished{butler2006, author = {Butler, Steve}, title = {Spectral Graph Theory: Applications of Courant Fischer}, year = {2006}, keywords = {graph, spectral, theory} }

%0 = unpublished %A = Butler, Steve %B = } %C = %D = 2006 %I = %T = Spectral Graph Theory: Applications of Courant Fischer} %U =

@unpublished{butler2006-3, author = {Butler, Steve}, title = {Spectral Graph Theory: Cheeger constants and discrepancy}, year = {2006}, keywords = {graph, introduction, spectral, theory} }

%0 = unpublished %A = Butler, Steve %B = } %C = %D = 2006 %I = %T = Spectral Graph Theory: Cheeger constants and discrepancy} %U =

@unpublished{butler2006-1, author = {Butler, Steve}, title = {Spectral Graph Theory: Three common spectra}, year = {2006}, keywords = {graph, introduction, spectral, theory} }

%0 = unpublished %A = Butler, Steve %B = } %C = %D = 2006 %I = %T = Spectral Graph Theory: Three common spectra} %U =

@article{cantador:bes, author = {Cantador, I. and Castells, P.}, title = {Building Emergent Social Networks and Group Profiles by Semantic User Preference Clustering}, year = {2006}, keywords = {clustering, community, detection, graph} }

%0 = article %A = Cantador, I. and Castells, P. %D = 2006 %T = Building Emergent Social Networks and Group Profiles by Semantic User Preference Clustering

@article{frivolt:cgc, author = {Frivolt, G. and Pok, O.}, title = {Comparison of Graph Clustering Approaches}, year = {2006}, keywords = {clustering, graph, survey} }

%0 = article %A = Frivolt, G. and Pok, O. %D = 2006 %T = Comparison of Graph Clustering Approaches

Social bookmark tools are rapidly emerging on the Web. In such systems users are setting up lightweight conceptual structures called folksonomies. The reason for their immediate success is the fact that no specific skills are needed for participating. At the moment, however, the information retrieval support is limited. We present a formal model and a new search algorithm for folksonomies,called FolkRank, that exploits the structure of the folksonomy. The proposed algorithm is also applied to findcommunities within the folksonomy and is used to structure search results. All findings are demonstrated on a large scale dataset.

@inproceedings{hotho2006information, author = {Hotho, Andreas and Jäschke, Robert and Schmitz, Christoph and Stumme, Gerd}, title = {Information Retrieval in Folksonomies: Search and Ranking}, editor = {Sure, York and Domingue, John}, booktitle = {The Semantic Web: Research and Applications}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, address = {Heidelberg}, year = {2006}, volume = {4011}, pages = {411-426}, keywords = {2006, folkrank, folksonomy, graph, iccs_example, information, l3s, mining, ol_web2.0, pagerank, rank, ranking, retrieval, search, seminar2006, testttag, trias_example, webzu, widely_related}, abstract = {Social bookmark tools are rapidly emerging on the Web. In such systems users are setting up lightweight conceptual structures called folksonomies. The reason for their immediate success is the fact that no specific skills are needed for participating. At the moment, however, the information retrieval support is limited. We present a formal model and a new search algorithm for folksonomies,called FolkRank, that exploits the structure of the folksonomy. The proposed algorithm is also applied to findcommunities within the folksonomy and is used to structure search results. All findings are demonstrated on a large scale dataset.} }

%0 = inproceedings %A = Hotho, Andreas and Jäschke, Robert and Schmitz, Christoph and Stumme, Gerd %B = The Semantic Web: Research and Applications %C = Heidelberg %D = 2006 %I = Springer %T = Information Retrieval in Folksonomies: Search and Ranking

Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.

@article{newman2006modularity, author = {Newman, M. E. J.}, title = {Modularity and community structure in networks}, journal = {Proceedings of the National Academy of Sciences}, year = {2006}, volume = {103}, number = {23}, pages = {8577--8582}, doi = {10.1073/pnas.0601602103}, keywords = {clustering, community, graph, modularity, network, structure}, abstract = {Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.} }

%0 = article %A = Newman, M. E. J. %D = 2006 %T = Modularity and community structure in networks

@article{newman2006fcs, author = {Newman, MEJ}, title = {Finding community structure in networks using the eigenvectors of matrices}, journal = {Physical Review E}, publisher = {APS}, year = {2006}, volume = {74}, number = {3}, pages = {36104}, keywords = {community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Newman, MEJ %D = 2006 %I = APS %T = Finding community structure in networks using the eigenvectors of matrices

@article{newman2006mac, author = {Newman, MEJ}, title = {Modularity and community structure in networks}, journal = {Proceedings of the National Academy of Sciences}, publisher = {National Acad Sciences}, year = {2006}, volume = {103}, number = {23}, pages = {8577--8582}, keywords = {community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Newman, MEJ %D = 2006 %I = National Acad Sciences %T = Modularity and community structure in networks

Recently, research projects such as PADLR and SWAP
have developed tools like Edutella or Bibster, which are targeted at
establishing peer-to-peer knowledge management (P2PKM) systems. In
such a system, it is necessary to obtain provide brief semantic
descriptions of peers, so that routing algorithms or matchmaking
processes can make decisions about which communities peers should
belong to, or to which peers a given query should be forwarded.
This paper provides a graph clustering technique on
knowledge bases for that purpose. Using this clustering, we can show
that our strategy requires up to 58% fewer queries than the
baselines to yield full recall in a bibliographic P2PKM scenario.

@inproceedings{schmitz2006content, author = {Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd}, title = {Content Aggregation on Knowledge Bases using Graph Clustering}, editor = {Sure, York and Domingue, John}, booktitle = {The Semantic Web: Research and Applications}, series = {LNAI}, publisher = {Springer}, address = {Heidelberg}, year = {2006}, volume = {4011}, pages = {530-544}, url = {http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf}, keywords = {2006, aggregation, clustering, content, graph, itegpub, l3s, myown, nepomuk, ontologies, ontology, seminar2006, theory}, abstract = {Recently, research projects such as PADLR and SWAP
have developed tools like Edutella or Bibster, which are targeted at
establishing peer-to-peer knowledge management (P2PKM) systems. In
such a system, it is necessary to obtain provide brief semantic
descriptions of peers, so that routing algorithms or matchmaking
processes can make decisions about which communities peers should
belong to, or to which peers a given query should be forwarded.
This paper provides a graph clustering technique on
knowledge bases for that purpose. Using this clustering, we can show
that our strategy requires up to 58% fewer queries than the
baselines to yield full recall in a bibliographic P2PKM scenario.} }

%0 = inproceedings %A = Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd %B = The Semantic Web: Research and Applications %C = Heidelberg %D = 2006 %I = Springer %T = Content Aggregation on Knowledge Bases using Graph Clustering %U = http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf

Recently, a variety of clustering algorithms have been proposed to handle data that is not linearly separable. Spectral clustering and kernel k-means are two such methods that are seemingly quite different. In this paper, we show that a general weighted kernel k-means objective is mathematically equivalent to a weighted graph partitioning objective. Special cases of this graph partitioning objective include ratio cut, normalized cut and ratio association. Our equivalence has important consequences: the weighted kernel k-means algorithm may be used to directly optimize the graph partitioning objectives, and conversely, spectral methods may be used to optimize the weighted kernel k-means objective. Hence, in cases where eigenvector computation is prohibitive, we eliminate the need for any eigenvector computation for graph partitioning. Moreover, we show that the Kernighan-Lin objective can also be incorporated into our framework, leading to an incremental weighted kernel k-means algorithm for local optim ization of the objective. We further discuss the issue of convergence of weighted kernel k-means for an arbitrary graph affinity matrix and provide a number of experimental results. These results show that non-spectral methods for graph partitioning are as effective as spectral methods and can be used for problems such as image segmentation in addition to data clustering.

@techreport{Dhillon:EtAl:05, author = {Dhillon, Inderjit S. and Guan, Yuqiang and Kulis, Brian}, title = {A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts}, year = {2005}, number = {TR-04-25}, url = {http://www.cs.utexas.edu/ftp/pub/techreports/tr04-25.pdf}, keywords = {community, detection, graph, k-means, spectral, theory}, abstract = {Recently, a variety of clustering algorithms have been proposed to handle data that is not linearly separable. Spectral clustering and kernel k-means are two such methods that are seemingly quite different. In this paper, we show that a general weighted kernel k-means objective is mathematically equivalent to a weighted graph partitioning objective. Special cases of this graph partitioning objective include ratio cut, normalized cut and ratio association. Our equivalence has important consequences: the weighted kernel k-means algorithm may be used to directly optimize the graph partitioning objectives, and conversely, spectral methods may be used to optimize the weighted kernel k-means objective. Hence, in cases where eigenvector computation is prohibitive, we eliminate the need for any eigenvector computation for graph partitioning. Moreover, we show that the Kernighan-Lin objective can also be incorporated into our framework, leading to an incremental weighted kernel k-means algorithm for local optim ization of the objective. We further discuss the issue of convergence of weighted kernel k-means for an arbitrary graph affinity matrix and provide a number of experimental results. These results show that non-spectral methods for graph partitioning are as effective as spectral methods and can be used for problems such as image segmentation in addition to data clustering. } }

%0 = techreport %A = Dhillon, Inderjit S. and Guan, Yuqiang and Kulis, Brian %B = } %C = %D = 2005 %I = %T = A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts} %U = http://www.cs.utexas.edu/ftp/pub/techreports/tr04-25.pdf

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.

@article{Dias2005240, author = {Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L.}, title = {Generating bicliques of a graph in lexicographic order}, journal = {Theoretical Computer Science}, year = {2005}, volume = {337}, number = {1-3}, pages = {240 - 248}, url = {http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280}, doi = {DOI: 10.1016/j.tcs.2005.01.014}, issn = {0304-3975}, keywords = {conp, graph, independent, set, theory}, abstract = {An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.} }

%0 = article %A = Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L. %D = 2005 %T = Generating bicliques of a graph in lexicographic order %U = http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280

@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

9.0. 9.0.1. Preliminaries 9.0.2. Role Graph 9.1. Structural Equivalence 9.1.1. Lattice of Equivalence Relations 9.1.2. Lattice of Structural Equivalences 9.1.3. Computation of Structural Equivalences 9.2. Regular Equivalence 9.2.1. Elementary Properties 9.2.2. Lattice Structure and Regular Interior 9.2.3. Computation of Regular Interior 9.2.4. The Role Assignment Problem 9.2.5. Existence of k-Role Assignments 9.3. Other Equivalences 9.3.1. Exact Role Assignments 9.3.2. Automorphic and Orbit Equivalence 9.3.3. Perfect Equivalence 9.3.4. Relative Regular Equivalence 9.4. Graphs with Multiple Relations 9.5. The Semigroup of a Graph 9.5.1. Winship-Pattison Role Equivalence 9.6. Chapter Notes

@incollection{lerner2005assignments, author = {Lerner, Jürgen}, title = {Role Assignments}, editor = {Brandes, Ulrik and Erlebach, Thomas}, booktitle = {Network Analysis}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, address = {Berlin / Heidelberg}, year = {2005}, volume = {3418}, pages = {216-252}, url = {http://dx.doi.org/10.1007/978-3-540-31955-9_9}, doi = {10.1007/978-3-540-31955-9_9}, keywords = {assignments, graph, lerner, network, roles, sna, social, structural}, abstract = {9.0. 9.0.1. Preliminaries 9.0.2. Role Graph 9.1. Structural Equivalence 9.1.1. Lattice of Equivalence Relations 9.1.2. Lattice of Structural Equivalences 9.1.3. Computation of Structural Equivalences 9.2. Regular Equivalence 9.2.1. Elementary Properties 9.2.2. Lattice Structure and Regular Interior 9.2.3. Computation of Regular Interior 9.2.4. The Role Assignment Problem 9.2.5. Existence of k-Role Assignments 9.3. Other Equivalences 9.3.1. Exact Role Assignments 9.3.2. Automorphic and Orbit Equivalence 9.3.3. Perfect Equivalence 9.3.4. Relative Regular Equivalence 9.4. Graphs with Multiple Relations 9.5. The Semigroup of a Graph 9.5.1. Winship-Pattison Role Equivalence 9.6. Chapter Notes} }

%0 = incollection %A = Lerner, Jürgen %B = Network Analysis %C = Berlin / Heidelberg %D = 2005 %I = Springer %T = Role Assignments %U = http://dx.doi.org/10.1007/978-3-540-31955-9_9

@article{white2005sca, author = {White, S. and Smyth, P.}, title = {A spectral clustering approach to finding communities in graph}, booktitle = {SIAM Data Mining}, year = {2005}, keywords = {community, detection, graph, spectral, theory} }

%0 = article %A = White, S. and Smyth, P. %B = SIAM Data Mining %D = 2005 %T = A spectral clustering approach to finding communities in graph

@article{an2004characterizing, author = {An, Yuan and Janssen, Jeannette and Milios, Evangelos E.}, title = {Characterizing and Mining the Citation Graph of the Computer Science Literature}, journal = {Knowl. Inf. Syst.}, publisher = {Springer-Verlag New York, Inc.}, address = {New York, NY, USA}, year = {2004}, volume = {6}, pages = {664--678}, url = {http://dx.doi.org/10.1007/s10115-003-0128-3}, doi = {http://dx.doi.org/10.1007/s10115-003-0128-3}, issn = {0219-1377}, keywords = {10th, Citation, characterizing, citation, computer, graph, mining} }

%0 = article %A = An, Yuan and Janssen, Jeannette and Milios, Evangelos E. %C = New York, NY, USA %D = 2004 %I = Springer-Verlag New York, Inc. %T = Characterizing and Mining the Citation Graph of the Computer Science Literature %U = http://dx.doi.org/10.1007/s10115-003-0128-3

We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately log n. We show that while this holds for m=1, for m=2 the diameter is asymptotically log n/log log n.
-

@article{keyhere, author = {Bollobás*, Béla and Riordan, Oliver}, title = {The Diameter of a Scale-Free Random Graph}, journal = {Combinatorica}, year = {2004}, volume = {24}, number = {1}, pages = {5--34}, url = {http://dx.doi.org/10.1007/s00493-004-0002-2}, keywords = {diameter, distance, geodesic, graph, mean, random}, abstract = {We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately log n. We show that while this holds for m=1, for m=2 the diameter is asymptotically log n/log log n. ER -} }

%0 = article %A = Bollobás*, Béla and Riordan, Oliver %D = 2004 %T = The Diameter of a Scale-Free Random Graph %U = http://dx.doi.org/10.1007/s00493-004-0002-2

@article{drineas2004clustering, author = {Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V.}, title = {Clustering large graphs via the singular value decomposition}, journal = {Machine Learning}, publisher = {Springer}, year = {2004}, volume = {56}, number = {1}, pages = {9--33}, url = {http://scholar.google.de/scholar.bib?q=info:gQY9HvWhsJcJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0}, keywords = {clustering, graph, svd, vldb} }

%0 = article %A = Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. %D = 2004 %I = Springer %T = Clustering large graphs via the singular value decomposition %U = http://scholar.google.de/scholar.bib?q=info:gQY9HvWhsJcJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0

@article{flake2004graph, author = {Flake, G.W. and Tarjan, R.E. and Tsioutsiouliklis, K.}, title = {Graph clustering and minimum cut trees}, journal = {Internet Mathematics}, publisher = {AK Peters}, year = {2004}, volume = {1}, number = {4}, pages = {385--408}, url = {http://scholar.google.de/scholar.bib?q=info:27hvFfjDdrkJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=6}, keywords = {clustering, community, detection, graph} }

%0 = article %A = Flake, G.W. and Tarjan, R.E. and Tsioutsiouliklis, K. %D = 2004 %I = AK Peters %T = Graph clustering and minimum cut trees %U = http://scholar.google.de/scholar.bib?q=info:27hvFfjDdrkJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=6

@article{langville2004deeper, author = {Langville, A.N. and Meyer, C.D.}, title = {Deeper inside pagerank}, journal = {Internet Mathematics}, publisher = {AK Peters}, year = {2004}, volume = {1}, number = {3}, pages = {335--380}, url = {http://scholar.google.de/scholar.bib?q=info:2bjOOHLGPW8J:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0}, keywords = {graph, pagerank} }

%0 = article %A = Langville, A.N. and Meyer, C.D. %D = 2004 %I = AK Peters %T = Deeper inside pagerank %U = http://scholar.google.de/scholar.bib?q=info:2bjOOHLGPW8J:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0

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

@article{brandes2003experiments, author = {Brandes, U. and Gaertler, M. and Wagner, D.}, title = {Experiments on graph clustering algorithms}, journal = {Lecture notes in computer science}, publisher = {Springer}, year = {2003}, pages = {568--579}, url = {http://scholar.google.de/scholar.bib?q=info:gDNQfOoSm6cJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=2}, keywords = {algorithm, clustering, community, detection, evaluation, graph} }

%0 = article %A = Brandes, U. and Gaertler, M. and Wagner, D. %D = 2003 %I = Springer %T = Experiments on graph clustering algorithms %U = http://scholar.google.de/scholar.bib?q=info:gDNQfOoSm6cJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=2

@article{estrada2003smb, author = {Estrada, E. and Rodriguez-Velázquez, J.A.}, title = {Spectral measures of bipartivity in complex networks}, journal = {SIAM Rev Phys Rev E}, publisher = {APS}, year = {2003}, volume = {72}, pages = {046105}, keywords = {bipartite, community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Estrada, E. and Rodriguez-Velázquez, J.A. %D = 2003 %I = APS %T = Spectral measures of bipartivity in complex networks

@article{haveliwala8090seg, author = {Haveliwala, T.H. and Kamvar, S.D.}, title = {The second eigenvalue of the Google matrix}, journal = {A Stanford University Technical Report http://dbpubs. stanford. edu}, year = {2003}, keywords = {graph, pagerank, spectral, theory} }

%0 = article %A = Haveliwala, T.H. and Kamvar, S.D. %D = 2003 %T = The second eigenvalue of the Google matrix

@article{New03, author = {Newman, M. E. J.}, title = {The structure and function of complex networks}, journal = {SIAM Review}, year = {2003}, volume = {45}, number = {2}, pages = {167-256}, keywords = {graph, introduction, network, review, survey, theory} }

%0 = article %A = Newman, M. E. J. %D = 2003 %T = The structure and function of complex networks

@article{verma2003csc, author = {Verma, D. and Meila, M.}, title = {A comparison of spectral clustering algorithms}, journal = {University of Washington, Tech. Rep. UW-CSE-03-05-01}, year = {2003}, keywords = {community, detection, graph, spectral, theory} }

%0 = article %A = Verma, D. and Meila, M. %D = 2003 %T = A comparison of spectral clustering algorithms

@inproceedings{yu2003multiclass, author = {Yu, Stella X. and Shi, Jianbo}, title = {Multiclass Spectral Clustering}, booktitle = {Proc. International Conference on Computer Vision (ICCV 03)}, address = {Nice, France}, year = {2003}, keywords = {Spectral, graph, partitioning, theory} }

%0 = inproceedings %A = Yu, Stella X. and Shi, Jianbo %B = Proc. International Conference on Computer Vision (ICCV 03) %C = Nice, France %D = 2003 %T = Multiclass Spectral Clustering

@unpublished{graphseparators02, author = {Blelloch, Guy}, title = {Graph Separators}, year = {2002}, keywords = {graph, separators, theory} }

%0 = unpublished %A = Blelloch, Guy %B = } %C = %D = 2002 %I = %T = Graph Separators} %U =

We describe a novel approach to visualize bibliographic networks that facilitates the simultaneous identification of clusters (e.g., topic areas) and prominent entities (e.g., surveys or landmark papers). While employing the landscape metaphor proposed in several earlier works, we introduce new means to determine relevant parameters of the landscape. Moreover, we are able to compute prominent entities, clustering of entities, and the landscape's surface in a surprisingly simple and uniform way. The effectiveness of our network visualizations is illustrated on data from the graph drawing literature.

@inproceedings{Brandes:2002:VBN:509740.509765, author = {Brandes, U. and Willhalm, T.}, title = {Visualization of bibliographic networks with a reshaped landscape metaphor}, booktitle = {Proceedings of the symposium on Data Visualisation 2002}, series = {VISSYM '02}, publisher = {Eurographics Association}, address = {Aire-la-Ville, Switzerland, Switzerland}, year = {2002}, pages = {159--ff}, url = {http://portal.acm.org/citation.cfm?id=509740.509765}, isbn = {1-58113-536-X}, keywords = {bibliographic, bibliography, citation, graph, networks, sna}, abstract = {We describe a novel approach to visualize bibliographic networks that facilitates the simultaneous identification of clusters (e.g., topic areas) and prominent entities (e.g., surveys or landmark papers). While employing the landscape metaphor proposed in several earlier works, we introduce new means to determine relevant parameters of the landscape. Moreover, we are able to compute prominent entities, clustering of entities, and the landscape's surface in a surprisingly simple and uniform way. The effectiveness of our network visualizations is illustrated on data from the graph drawing literature.} }

%0 = inproceedings %A = Brandes, U. and Willhalm, T. %B = Proceedings of the symposium on Data Visualisation 2002 %C = Aire-la-Ville, Switzerland, Switzerland %D = 2002 %I = Eurographics Association %T = Visualization of bibliographic networks with a reshaped landscape metaphor %U = http://portal.acm.org/citation.cfm?id=509740.509765

@article{snijders2002mcm, author = {Snijders, T.A.B.}, title = {Markov chain Monte Carlo estimation of exponential random graph models}, journal = {Journal of Social Structure}, year = {2002}, volume = {3}, number = {2}, pages = {1--40}, keywords = {carlo, estimation, exponential, generation, graph, model, monte, p*, parameter, sna} }

%0 = article %A = Snijders, T.A.B. %D = 2002 %T = Markov chain Monte Carlo estimation of exponential random graph models

@article{soderberg2002gfi, author = {Soderberg, B.}, title = {General formalism for inhomogeneous random graphs}, journal = {Phys. Rev. E}, publisher = {APS}, year = {2002}, volume = {66}, number = {6}, pages = {066121}, keywords = {graph, k-partite, random, theory} }

%0 = article %A = Soderberg, B. %D = 2002 %I = APS %T = General formalism for inhomogeneous random graphs

@inproceedings{coclustering01, author = {Dhillon, Inderjit S.}, title = {Co-clustering documents and words using bipartite spectral graph partitioning}, booktitle = {KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM Press}, address = {New York, NY, USA}, year = {2001}, pages = {269--274}, url = {http://portal.acm.org/citation.cfm?id=502512.502550}, doi = {10.1145/502512.502550}, isbn = {158113391X}, keywords = {community, detection, graph, spectral, theory} }

%0 = inproceedings %A = Dhillon, Inderjit S. %B = KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2001 %I = ACM Press %T = Co-clustering documents and words using bipartite spectral graph partitioning %U = http://portal.acm.org/citation.cfm?id=502512.502550

@misc{Monien_onspectral, author = {Monien, B.}, title = {On Spectral Bounds for the k-Partitioning of Graphs}, year = {2001}, keywords = {graph, spectral, theory} }

%0 = misc %A = Monien, B. %B = } %C = %D = 2001 %I = %T = On Spectral Bounds for the k-Partitioning of Graphs} %U =

@article{newman2001rga, author = {Newman, MEJ and Strogatz, SH and Watts, DJ}, title = {Random graphs with arbitrary degree distributions and their applications}, journal = {Arxiv preprint cond-mat/0007235}, year = {2001}, keywords = {configuration, degree, distribution, function, generating, graph, model, random} }

%0 = article %A = Newman, MEJ and Strogatz, SH and Watts, DJ %D = 2001 %T = Random graphs with arbitrary degree distributions and their applications

Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1

@inproceedings{Ng01onspectral, author = {Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair}, title = {On spectral clustering: Analysis and an algorithm}, booktitle = {Advances in Neural Information Processing Systems 14}, publisher = {MIT Press}, year = {2001}, pages = {849--856}, keywords = {clustering, community, detection, graph, spectral, theory}, abstract = {Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1} }

%0 = inproceedings %A = Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair %B = Advances in Neural Information Processing Systems 14 %D = 2001 %I = MIT Press %T = On spectral clustering: Analysis and an algorithm

@article{aiello2000random, author = {Aiello, W. and Chung, F. and Lu, L.}, title = {A random graph model for massive graphs}, booktitle = {Proceedings of the thirty-second annual ACM symposium on Theory of computing}, year = {2000}, pages = {171--180}, url = {http://scholar.google.de/scholar.bib?q=info:iG723gINfRAJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0}, keywords = {graph, pagerank, random, simrank, surfer} }

%0 = article %A = Aiello, W. and Chung, F. and Lu, L. %B = Proceedings of the thirty-second annual ACM symposium on Theory of computing %D = 2000 %T = A random graph model for massive graphs %U = http://scholar.google.de/scholar.bib?q=info:iG723gINfRAJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0

@article{butler:cgb, author = {Butler, S.}, title = {Cospectral graphs for both the adjacency and normalized Laplacian matrices}, year = {2000}, keywords = {bipartite, graph, spectral, theory} }

%0 = article %A = Butler, S. %D = 2000 %T = Cospectral graphs for both the adjacency and normalized Laplacian matrices

We describe a package of practical tools and libraries for manipulating graphs and their drawings. Our design, which aimed at facilitating the combination of the package components with other tools, includes stream and event interfaces for graph operations, high-quality static and dynamic layout algorithms, and the ability to handle sizable graphs. We conclude with a description of the applications of this package to a variety of software engineering tools.

@article{gansner2000graph, author = {Gansner, Emden R. and North, Stephen C.}, title = {An open graph visualization system and its applications to software engineering}, journal = {Software Practice & Experience}, publisher = {John Wiley & Sons, Inc.}, address = {New York, NY, USA}, year = {2000}, volume = {30}, number = {11}, pages = {1203--1233}, url = {http://dl.acm.org/citation.cfm?id=358668.358697}, doi = {10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.3.CO;2-E}, issn = {0038-0644}, keywords = {drawing, graph, graphics, graphviz, visualization}, abstract = {We describe a package of practical tools and libraries for manipulating graphs and their drawings. Our design, which aimed at facilitating the combination of the package components with other tools, includes stream and event interfaces for graph operations, high-quality static and dynamic layout algorithms, and the ability to handle sizable graphs. We conclude with a description of the applications of this package to a variety of software engineering tools.} }

%0 = article %A = Gansner, Emden R. and North, Stephen C. %C = New York, NY, USA %D = 2000 %I = John Wiley & Sons, Inc. %T = An open graph visualization system and its applications to software engineering %U = http://dl.acm.org/citation.cfm?id=358668.358697

@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

@unpublished{ranade:sus, author = {Ranade, A.G.}, title = {Some uses of spectral methods}, year = {2000}, keywords = {clustering, graph, spectral, svd, theory} }

%0 = unpublished %A = Ranade, A.G. %B = } %C = %D = 2000 %I = %T = Some uses of spectral methods} %U =

@article{anderson1999ppl, author = {Anderson, C.J. and Wasserman, S. and Crouch, B.}, title = {A p* primer: Logit models for social networks}, journal = {Social Networks}, publisher = {Elsevier}, year = {1999}, volume = {21}, number = {1}, pages = {37--66}, keywords = {carlo, exponential, generation, graph, model, monte, random, simulation, sna} }

%0 = article %A = Anderson, C.J. and Wasserman, S. and Crouch, B. %D = 1999 %I = Elsevier %T = A p* primer: Logit models for social networks

Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

@article{citeulike:90557, author = {Barabasi, A. L. and Albert, R.}, title = {Emergence of scaling in random networks}, journal = {Science}, address = {Department of Physics, University of Notre Dame, Notre Dame, IN 46556, USA.}, year = {1999}, volume = {286}, number = {5439}, pages = {509--512}, url = {http://view.ncbi.nlm.nih.gov/pubmed/10521342}, issn = {0036-8075}, keywords = {graph, network, properties, statistics}, abstract = {Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.} }

%0 = article %A = Barabasi, A. L. and Albert, R. %C = Department of Physics, University of Notre Dame, Notre Dame, IN 46556, USA. %D = 1999 %T = Emergence of scaling in random networks %U = http://view.ncbi.nlm.nih.gov/pubmed/10521342

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

In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://infolab.stanford.edu/~backrub/google.html To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from three years ago. This paper provides an in-depth description of our large-scale web search engine - the first such detailed public description w...

@inproceedings{Brin98theanatomy, author = {Brin, Sergey and Page, Lawrence}, title = {The Anatomy of a Large-Scale Hypertextual Web Search Engine}, booktitle = {Computer Networks and ISDN Systems}, year = {1998}, pages = {107--117}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3243}, keywords = {graph, pagerank}, abstract = {In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://infolab.stanford.edu/~backrub/google.html To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from three years ago. This paper provides an in-depth description of our large-scale web search engine -- the first such detailed public description w...} }

%0 = inproceedings %A = Brin, Sergey and Page, Lawrence %B = Computer Networks and ISDN Systems %D = 1998 %T = The Anatomy of a Large-Scale Hypertextual Web Search Engine %U = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3243

@article{guattery1998qss, author = {Guattery, S. and Miller, G.L.}, title = {On the quality of spectral separators}, journal = {SIAM Journal on Matrix Analysis and Applications}, publisher = {[Philadelphia, Pa.: The Society, c1988-}, year = {1998}, volume = {19}, number = {3}, pages = {701--719}, keywords = {graph, spectral, theory} }

%0 = article %A = Guattery, S. and Miller, G.L. %D = 1998 %I = [Philadelphia, Pa.: The Society, c1988- %T = On the quality of spectral separators

In this paper, we present a new multilevel k-way hypergraph partitioning algorithm that substantially outperforms the existing state-of-the-art K-PM/LR algorithm for multi-way partitioning. both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those produced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the (K - 1) metric. Furthermore, our algorithm is significantly faster, requiring 4 to 5 times less time than that required by K-PM/LR. 1 Introduction Hypergraph partitioning is an important problem with extensive application to many areas, including VLSI design [10], efficient storage of large databases on disks [14], and data mining [13]. The problem is to partition the vertices of a hypergraph into k roughly equal parts, such that a certain objective function defined over the hyperedges is optimized. A commonly used obje...

@inproceedings{Karypis98multilevelk-way, author = {Karypis, George and Kumar, Vipin}, title = {Multilevel k-way Hypergraph Partitioning}, booktitle = {In Proceedings of the Design and Automation Conference}, year = {1998}, pages = {343--348}, keywords = {clustering, community, detection, graph, hypergraph, partitioning}, abstract = {In this paper, we present a new multilevel k-way hypergraph partitioning algorithm that substantially outperforms the existing state-of-the-art K-PM/LR algorithm for multi-way partitioning. both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those produced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the (K - 1) metric. Furthermore, our algorithm is significantly faster, requiring 4 to 5 times less time than that required by K-PM/LR. 1 Introduction Hypergraph partitioning is an important problem with extensive application to many areas, including VLSI design [10], efficient storage of large databases on disks [14], and data mining [13]. The problem is to partition the vertices of a hypergraph into k roughly equal parts, such that a certain objective function defined over the hyperedges is optimized. A commonly used obje...} }

%0 = inproceedings %A = Karypis, George and Kumar, Vipin %B = In Proceedings of the Design and Automation Conference %D = 1998 %T = Multilevel k-way Hypergraph Partitioning

@book{Chung:1997, author = {Chung, F. R. K.}, title = {Spectral Graph Theory}, publisher = {American Mathematical Society}, year = {1997}, keywords = {graph, spectral, theory} }

%0 = book %A = Chung, F. R. K. %D = 1997 %I = American Mathematical Society %T = Spectral Graph Theory

@article{karypis1997mhp, author = {Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S.}, title = {Multilevel hypergraph partitioning: Application in VLSI domain}, booktitle = {Proceedings of the 34th annual conference on Design automation}, year = {1997}, pages = {526--529}, keywords = {clustering, community, detection, graph, hypergraph} }

%0 = article %A = Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S. %B = Proceedings of the 34th annual conference on Design automation %D = 1997 %T = Multilevel hypergraph partitioning: Application in VLSI domain

@article{mohar1997sal, author = {Mohar, B.}, title = {Some applications of Laplace eigenvalues of graphs}, journal = {Graph Symmetry: Algebraic Methods and Applications}, publisher = {Kluwer}, year = {1997}, volume = {497}, pages = {227--275}, keywords = {graph, laplacian, spectral, survey, theory} }

%0 = article %A = Mohar, B. %D = 1997 %I = Kluwer %T = Some applications of Laplace eigenvalues of graphs

@techreport{Spielman:1996, author = {Spielman, Daniel A. and Teng, Shang}, title = {Spectral Partitioning Works: Planar Graphs and Finite Element Meshes}, publisher = {University of California at Berkeley}, address = {Berkeley, CA, USA}, year = {1996}, keywords = {clustering, community, detection, graph, spectral, survey, theory} }

%0 = techreport %A = Spielman, Daniel A. and Teng, Shang %B = } %C = Berkeley, CA, USA %D = 1996 %I = University of California at Berkeley %T = Spectral Partitioning Works: Planar Graphs and Finite Element Meshes} %U =

@inproceedings{Alpert95spectralpartitioning:, author = {Alpert, Charles J. and Kahng, Andrew B. and zen Yao, So}, title = {Spectral partitioning: The more eigenvectors, the better}, booktitle = {Proc. ACM/IEEE Design Automation Conf}, year = {1995}, pages = {195--200}, keywords = {community, detection, graph, spectral, theory} }

%0 = inproceedings %A = Alpert, Charles J. and Kahng, Andrew B. and zen Yao, So %B = Proc. ACM/IEEE Design Automation Conf %D = 1995 %T = Spectral partitioning: The more eigenvectors, the better

@misc{molloy_reed95, author = {Molloy, M. and Reed, B.}, title = {A critical point for random graphs with a given degree sequence}, journal = {Random Structures & Algorithms}, year = {1995}, volume = {6}, pages = {161-179}, url = {/brokenurl#citeseer.ist.psu.edu/molloy95critical.html}, keywords = {component, configuration, giant, graph, model, random, theory} }

%0 = misc %A = Molloy, M. and Reed, B. %B = } %C = %D = 1995 %I = %T = A critical point for random graphs with a given degree sequence} %U = /brokenurl#citeseer.ist.psu.edu/molloy95critical.html

@article{179359, author = {Bolla, Marianna and Tusnády, Gábor}, title = {Spectra and optimal partitions of weighted graphs}, journal = {Discrete Math.}, publisher = {Elsevier Science Publishers B. V.}, address = {Amsterdam, The Netherlands, The Netherlands}, year = {1994}, volume = {128}, number = {1-3}, pages = {1--20}, url = {http://portal.acm.org/citation.cfm?id=179357.179359}, doi = {http://dx.doi.org/10.1016/0012-365X(94)90100-7}, issn = {0012-365X}, keywords = {graph, spectral, the} }

%0 = article %A = Bolla, Marianna and Tusnády, Gábor %C = Amsterdam, The Netherlands, The Netherlands %D = 1994 %I = Elsevier Science Publishers B. V. %T = Spectra and optimal partitions of weighted graphs %U = http://portal.acm.org/citation.cfm?id=179357.179359

@article{journals/tcad/ChanSZ94, author = {Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.}, title = {Spectral K-way ratio-cut partitioning and clustering.}, journal = {IEEE Trans. on CAD of Integrated Circuits and Systems}, year = {1994}, volume = {13}, number = {9}, pages = {1088-1096}, url = {http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94}, keywords = {community, detection, graph, partitioning, spectral, theory} }

%0 = article %A = Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y. %D = 1994 %T = Spectral K-way ratio-cut partitioning and clustering. %U = http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94

@article{journals/tcad/HagenK92, author = {Hagen, Lars W. and Kahng, Andrew B.}, title = {New spectral methods for ratio cut partitioning and clustering.}, journal = {IEEE Trans. on CAD of Integrated Circuits and Systems}, year = {1992}, volume = {11}, number = {9}, pages = {1074-1085}, url = {http://dblp.uni-trier.de/db/journals/tcad/tcad11.html#HagenK92}, keywords = {graph, partitioning, spectral, theory} }

%0 = article %A = Hagen, Lars W. and Kahng, Andrew B. %D = 1992 %T = New spectral methods for ratio cut partitioning and clustering. %U = http://dblp.uni-trier.de/db/journals/tcad/tcad11.html#HagenK92

@article{mohar1991lsg, author = {Mohar, B.}, title = {The Laplacian spectrum of graphs}, journal = {Graph Theory, Combinatorics, and Applications}, publisher = {New York: Wiley}, year = {1991}, volume = {2}, pages = {871--898}, keywords = {graph, laplacian, spectral, survey, theory} }

%0 = article %A = Mohar, B. %D = 1991 %I = New York: Wiley %T = The Laplacian spectrum of graphs

@article{partitioning89, author = {Pothen, A. and Simon, H.D. and Liou, K.P.}, title = {Partitioning Sparse Matrices with Eigenvectors of Graphs}, journal = {SIAM J. MATRIX ANAL. APPLIC.}, year = {1990}, volume = {11}, number = {3}, pages = {430--452}, url = {http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf }, keywords = {clustering, community, graph, partitioning, spectral, theory} }

%0 = article %A = Pothen, A. and Simon, H.D. and Liou, K.P. %D = 1990 %T = Partitioning Sparse Matrices with Eigenvectors of Graphs %U = http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf

@article{frank1988rsa, author = {Frank, O.}, title = {Random sampling and social networks: a survey of various approaches}, journal = {Math. Sci. Humaines}, year = {1988}, volume = {104}, pages = {19--33}, keywords = {graph, random, review, sna, theory} }

%0 = article %A = Frank, O. %D = 1988 %T = Random sampling and social networks: a survey of various approaches

@article{46243, author = {Johnson, David S. and Papadimitriou, Christos H.}, title = {On generating all maximal independent sets}, journal = {Inf. Process. Lett.}, publisher = {Elsevier North-Holland, Inc.}, address = {Amsterdam, The Netherlands, The Netherlands}, year = {1988}, volume = {27}, number = {3}, pages = {119--123}, url = {http://portal.acm.org/citation.cfm?id=46241.46243}, doi = {http://dx.doi.org/10.1016/0020-0190(88)90065-8}, issn = {0020-0190}, keywords = {complexity, graph, independent, sets, theory} }

%0 = article %A = Johnson, David S. and Papadimitriou, Christos H. %C = Amsterdam, The Netherlands, The Netherlands %D = 1988 %I = Elsevier North-Holland, Inc. %T = On generating all maximal independent sets %U = http://portal.acm.org/citation.cfm?id=46241.46243

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

@article{karonski1982rrg, author = {Karonski, M.}, title = {A review of random graphs}, journal = {Journal of Graph Theory}, publisher = {Wiley Subscription Services, Inc., A Wiley Company New York}, year = {1982}, volume = {6}, number = {4}, keywords = {graph, random, theory} }

%0 = article %A = Karonski, M. %D = 1982 %I = Wiley Subscription Services, Inc., A Wiley Company New York %T = A review of random graphs

@article{bollobas1981drg, author = {Bollobas, B.}, title = {The diameter of random graphs}, journal = {Transactions of the American Mathematical Society}, publisher = {American Mathematical Society}, year = {1981}, pages = {41--52}, keywords = {diameter, graph, random} }

%0 = article %A = Bollobas, B. %D = 1981 %I = American Mathematical Society %T = The diameter of random graphs

A Family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced. These measures define centrality in terms of the degree to which a point falls on the shortest path between others and therefore has a potential for control of communication. They may be used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected.

@article{citeulike:1025135, author = {Freeman, Linton C.}, title = {A Set of Measures of Centrality Based on Betweenness}, journal = {Sociometry}, publisher = {American Sociological Association}, year = {1977}, volume = {40}, number = {1}, pages = {35--41}, url = {http://links.jstor.org/sici?sici=0038-04318197703940A1C35AASOMOCE2.0.COB2-H}, keywords = {betweeness, centrality, graph, sna, theory}, abstract = {A Family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced. These measures define centrality in terms of the degree to which a point falls on the shortest path between others and therefore has a potential for control of communication. They may be used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected.} }

%0 = article %A = Freeman, Linton C. %D = 1977 %I = American Sociological Association %T = A Set of Measures of Centrality Based on Betweenness %U = http://links.jstor.org/sici?sici=0038-04318197703940A1C35AASOMOCE2.0.COB2-H

@article{fiedler1975pen, author = {Fiedler, M.}, title = {A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory}, journal = {Czechoslovak Mathematical Journal}, year = {1975}, volume = {25}, number = {100}, pages = {619--633}, keywords = {graph, spectral, theory} }

%0 = article %A = Fiedler, M. %D = 1975 %T = A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory

@article{donath1973lbp, author = {Donath, W.E. and Hoffman, A.J.}, title = {Lower bounds for the partitioning of graphs}, journal = {IBM Journal of Research and Development}, year = {1973}, volume = {17}, number = {5}, pages = {420--425}, keywords = {clustering, community, detection, graph, spectral, theory} }

%0 = article %A = Donath, W.E. and Hoffman, A.J. %D = 1973 %T = Lower bounds for the partitioning of graphs