2 Search Results for "Schweitzer, Frank"


Document
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

Authors: Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
It is well known that the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional Weisfeiler-Leman algorithm (2-WL). On the other hand, the prominent Cai-Fürer-Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph G of color multiplicity 4, recognizes whether or not G is identifiable by 2-WL, that is, whether or not 2-WL distinguishes G from any non-isomorphic graph. In fact, we solve the more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to directed graphs of color multiplicity 4 with colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai-Fürer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Fürer-Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as (n₃)-configurations in incidence geometry.

Cite as

Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fuhlbruck_et_al:LIPIcs.STACS.2020.43,
  author =	{Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg},
  title =	{{Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.43},
  URN =		{urn:nbn:de:0030-drops-119046},
  doi =		{10.4230/LIPIcs.STACS.2020.43},
  annote =	{Keywords: Graph Isomorphism, Weisfeiler-Leman Algorithm, Cai-F\"{u}rer-Immerman Graphs, coherent Configurations}
}
Document
A Quantitative Study of Social Organisation in Open Source Software Communities

Authors: Marcelo Serrano Zanetti, Emre Sarigöl, Ingo Scholtes, Claudio Juan Tessone, and Frank Schweitzer

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop


Abstract
The success of open source projects crucially depends on the voluntary contributions of a sufficiently large community of users. Apart from the mere size of the community, interesting questions arise when looking at the evolution of structural features of collaborations between community members. In this article, we discuss several network analytic proxies that can be used to quantify different aspects of the social organisation in social collaboration networks. We particularly focus on measures that can be related to the cohesiveness of the communities, the distribution of responsibilities and the resilience against turnover of community members. We present a comparative analysis on a large-scale dataset that covers the full history of collaborations between users of $14$ major open source software communities. Our analysis covers both aggregate and time-evolving measures and highlights differences in the social organisation across communities. We argue that our results are a promising step towards the definition of suitable, potentially multi-dimensional, resilience and risk indicators for open source software communities.

Cite as

Marcelo Serrano Zanetti, Emre Sarigöl, Ingo Scholtes, Claudio Juan Tessone, and Frank Schweitzer. A Quantitative Study of Social Organisation in Open Source Software Communities. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 116-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{serranozanetti_et_al:OASIcs.ICCSW.2012.116,
  author =	{Serrano Zanetti, Marcelo and Sarig\"{o}l, Emre and Scholtes, Ingo and Tessone, Claudio Juan and Schweitzer, Frank},
  title =	{{A Quantitative Study of Social Organisation in Open Source Software Communities}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{116--122},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.116},
  URN =		{urn:nbn:de:0030-drops-37748},
  doi =		{10.4230/OASIcs.ICCSW.2012.116},
  annote =	{Keywords: open source software, mining software repositories, social networks}
}
  • Refine by Author
  • 1 Fuhlbrück, Frank
  • 1 Köbler, Johannes
  • 1 Sarigöl, Emre
  • 1 Scholtes, Ingo
  • 1 Schweitzer, Frank
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Cai-Fürer-Immerman Graphs
  • 1 Graph Isomorphism
  • 1 Weisfeiler-Leman Algorithm
  • 1 coherent Configurations
  • 1 mining software repositories
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail