Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
Community detection in graphs has been the subject of many algorithms. Recent methods want to optimize a modularity function which shows a maximum of relationships within communities and found a minimum of inter-community relations. these algorithms are applied to unipartite, multipartite and directed graphs. However, given the NP-completeness of the problem, these algorithms are heuristics that do not guarantee an optimum. In this paper we introduce an algorithm which, based on an approximate solution obtained through a efficient detection algorithm, modifie it to achieve a local optimum based on a function. this reassignment function is a potential function and therefore the computed optimum is a Nash equilibrium. We supplement our method with an overlap function that allows to have simultaneously the two detection modes. Several experiments show the interest of our approach.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Repr\'esentation du genre dans des donn\'ees open source de parole (Gender representation in open source speech resources 1 With the rise of artificial intelligence (AI) and the growing use of deep-learning architectures, the question of ethics and transparency in AI systems has become a central concern within the research community)
Avec l{'}essor de l{'}intelligence artificielle (IA) et l{'}utilisation croissante des architectures d{'}apprentissage profond, la question de l{'}{\'e}thique et de la transparence des syst{\`e}mes d{'}IA est devenue une…
EthicsD\'etection de conflits dans les communaut\'es \'epist\'emiques en ligne (Conflicts detection in online epistemic communities) [in French]
Apprentissage de plongements lexicaux par une approche r\'eseaux complexes (Complex networks based word embeddings)
La litt{\'e}rature des r{\'e}seaux complexes a montr{\'e} la pertinence de l{'}{\'e}tude de la langue sous forme de r{\'e}seau pour diff{\'e}rentes applications : d{\'e}sambigu{\"\i}sation, r{\'e}sum{\'e} automatique, cl…
Word EmbeddingsConstruire des ressources collaboratives pour les langues peu dotées: une modélisation orientée communauté (Building collaborative resources for poorly endowed languages : community-oriented modeling )
Les applications du traitement automatique des langues (TAL) nourrissent aujourd’hui une bonne partie des langues indo-européennes en raison des corpus linguistiques de qualité disponibles en grande quantité et variété. …
OKM: une extension des k-moyennes pour la recherche de classes recouvrantes.
Dans cet article nous abordons le problème de la classification (ou clustering) dans le but de découvrir des classes avec recouvrements. Malgré quelques avancées récentes dans ce domaines, motivées par des besoins applic…
Classification