Mostrar código-fonte de Estrutura comunitária

Em [[ciência das redes]], uma [[Teoria_das_redes_complexas|rede]] tem '''estrutura comunitária''' se os nós dessa rede podem ser divididos em conjuntos onde os nós são densamente conectados internamente. Esses conjuntos podem ter sobreposição ou serem disjuntos. No caso disjunto, é assumido que os nós são esparsamente conectados com os nós de outros conjuntos. De forma geral, é mais provável um nó em uma rede com estrutura comunitária tenha uma aresta com outro nó de sua(s) comunidade(s) do que outros nós na rede, em contraste com [[Teoria_das_redes_complexas#Rede_aleatória|redes aleatórias]] onde todo par de nós tem a mesma chance de ter uma ligação.

==Definição==

[[Image:Network Community Structure.svg|right|thumb|Fig. 1: Ilustração de uma [[Teoria das redes complexas|rede]] evidenciando '''estruturas comunitárias''', onde há três grupos com interligações densas internamente e esparsas entre os grupos.]]

===Comunidades disjuntas===

Nessa seção, vamos considerar apenas estruturas de comunidade disjuntas. Os primeiros trabalhos sobre estrutura comunitária disjunta assumiam que as comunidades eram [[clique]]s<ref name="luce1949method">{{citar artigo
|título=A method of matrix analysis of group structure
|autor=Luce, R Duncan and Perry, Albert
|publicado=Psychometrika
|ano=1948
|editora=Springer}}</ref>. De fato, cliques são [[subgrafo]]s densos na rede, isso constitui uma comunidade. Por outro lado, definir comunidades somente como cliques é muito restritivo porque geralmente em redes complexas é raro cliques de número de nós superiores a três e podemos deixar de classificar comunidades legítimas<ref name="barabasilivro">
{{citar artigo
|título=Network science
|autor=Barabási, Albert-László
|revista=Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences,
|volume=371,
|número=1987
|ano=2013,
|editora=The Royal Society Publishing}}</ref>. Por exemplo, na Fig. 1 à direita, nenhuma das comunidades destacadas são cliques.

Para relaxar a definição de comunidades através de cliques, foram propostas duas definições: ''comunidades fortes'' e ''comunidades fracas''<ref name="radicchi2004">{{citar artigo
|título=Defining and identifying communities in networks
|autor=Radicchi Filippo and Castellano, Claudio and Cecconi, Federico and Loreto, Vittorio and Parisi, Domenico
|revista=Proceedings of the national academy of sciences
|volume=101
|número=9
|ano=2004
|editora=National Acad Sciences
}}</ref>. Dada uma rede representada por um [[grafo]] <math>G = (V, E)</math>, é denotado como <math>\deg(i)</math> o [[Grau_(teoria_dos_grafos)|grau]] do vértice <math>i\in V</math>. Seja <math>S \subset G</math> um subgrafo tal que <math>i\in S</math>, vamos chamar de <math>\deg^{in}_S(i)</math> o número de arestas conectado o nó <math>i</math> com os nós em <math>S</math>. E similarmente, <math>\deg^{out}_S(i)</math> o número de arestas conectando o nó <math>i</math> com os nós não pertencentes a <math>S</math>.

====Comunidades fortes====

O [[subgrafo]] <math>S\subset G</math> é uma ''comunidade forte'' se
<math display="block">\deg^{in}_S(i) > \deg^{out}_S(i), \,\, \forall i \in S.</math>
Em outras palavras, todo nó pertencente a uma comunidade forte tem mais ligações internas em relação a comunidade do que externas.

====Comunidades fracas====

O [[subgrafo]] <math>S\subset G</math> é uma ''comunidade fraca'' se
<math display="block">\sum_{i\in S} \deg^{in}_S(i) > \sum_{i\in S}\deg^{out}_S(i).</math>
Nas comunidades fracas, a soma de todos os graus internos de <math>S</math> é maior que a soma dos graus externos. Note que todo clique é uma comunidade forte e toda comunidade forte também é uma comunidade fraca. Por outro lado, comunidades fracas nem sempre são comunidades fortes.

É possível observar que há diversas definições para comunidades, algumas mais restritivas como definir comunidades como cliques e outras menos, como comunidades fortes e fracas. Adicionalmente, há diversas outras formas de definir comunidades que podem ser mais apropriadas dependendo do contexto<ref name="scott1988">{{citar artigo
|título=Social network analysis,
|autor=Scott, John,
|revista=Sociology,
|volume=22,
|número=1,
|ano=1988,
|editora=British Sociological Association Publications Limited
}}</ref>.

==Modularidade==

Em redes aleatórias, não é possível observar nenhum tipo de estrutura comunitária, pois é esperado que as chances de ligações ocorram de forma uniforme por todos os nós. Através dessa observação, é possível criar uma métrica de modularidade calculando a diferença do padrão de ligações com de uma rede aleatória. Dessa forma, é possível medir quantitativamente se uma partição tem estrutura de comunitária.

Vamos supor uma [[Teoria das redes complexas|rede]] representada pelo [[grafo]] <math>G = (V, E)</math> com a [[matriz de adjacência]] <math>A = \left[ a_{ij} \right]</math> e uma partição da rede em comunidades <math>\mathcal{S} = \{S_1, \dots, S_{m}\}</math>. Note que <math>S_i</math> é um [[subgrafo]], vamos denotar como <math>E(S_i)</math> o número de links internos da comunidade <math>S_i</math> e <math>\deg(S_i)</math> a soma do graus dos nós em <math>S_i</math> em relação a <math>G</math>. Para cada comunidade <math>c = \{1, \dots, m\}</math>, podemos definir a diferença entre suas ligações em <math>A</math> e o número esperado de ligações <math>p_{ij}</math> entre dois nós <math>i</math> e <math>j</math> caso a rede fosse aleatória:
<math display=block>M_c = \frac{1}{2|E|} \sum_{(i, j) \in S_c} \left(a_{ij} - p_{ij}\right)</math>
Em uma rede aleatória, a probabilidade de dois nós <math>u</math> e <math>v</math> estarem conectados é
<math display=block>p_{ij} = \frac{\deg(i)\deg(j)}{2L},</math>
então, a ''modularidade'' da rede toda é
<math display=block>
M = \frac{1}{2|E|} \sum_{i=0}^N\sum_{j=1}^N \left(a_{ij} - \frac{\deg(i)\deg(j)}{2|E|}\right) \delta_{ij}
</math>
onde <math>\delta_{ij}</math> é <math>1</math> caso os nós <math>i</math> e <math>j</math> pertencem a mesma comunidade e <math>0</math> caso o contrário. Dessa forma, apenas os nós que estão na mesma comunidade serão considerados, então podemos reescrever a ''modularidade'' como
<math display=block>
\begin{align}
M	&= \frac{1}{2|E|} \sum_{i,j = 1}^N A_{ij}\delta_{ij} - \frac{1}{2|E|} \frac{\deg(i)\deg(j)}{2|E|}\delta_{ij} \\
	&= \sum_{c=1}^{m} \frac{1}{2|E|} \sum_{i,j \in S_c} A_{ij} - \sum_{c=1}^{m}\frac{1}{(2|E|)^2} \sum_{i,j \in S_c} \deg(i)\deg(j) \\
	&= \sum_{c=1}^{m} \frac{L(S_c)}{|E|} - \sum_{c=1}^{m}\frac{\deg(S_c)^2}{4|E|^2} \\
	&= \sum_{c = 1}^{m} \left[ \frac{L(S_c)}{|E|} - \left(\frac{\deg(S_c)}{2|E|}\right)^2 \right].
\end{align}
</math>
Quanto maior for a modularidade, melhor <math>\mathcal{S}</math> representa uma partição de <math>G</math> em comunidades. Também, <math>M</math> é sempre menor que 1<ref name=DDD2005></ref><ref name=Fortunato2007></ref>.

==Algoritmos para encontrar comunidades==

Encontrar comunidades em uma [[Teoria_das_redes_complexas|rede]] arbitrária pode ser difícil [[Complexidade computacional|computacionalmente]]. Normalmente, o número de comunidades é desconhecido a priori e as comunidades tem diferentes tamanhos e densidade de ligações. Apesar dessas dificuldades, algoritmos foram desenvolvidos com essa finalidade<ref name=Notices>
{{cite journal
	|author1=M. A. Porter |author2=J.-P. Onnela |author3=P. J. Mucha | year = 2009
	| title = Communities in Networks
	| journal =  	Notices of the American Mathematical Society
	| volume = 56
	| pages = 1082–1097, 1164–1166
	| url = http://www.ams.org/notices/200909/rtx090901082p.pdf
}}</ref>.

===Método por corte mínimo===

O método por [[Corte Mínimo|corte mínimo]], a rede é dividida em um número pré-determinado de comunidades, onde essas comunidades normalmente tem tamanhos iguais. Essas comunidades são escolhidas de tal forma que o número de arestas entre os grupos é minimizado. Esse método funciona bem para várias aplicações mas não tem resultados satisfatórios para redes no geral porque o método encontrará comunidades sem levar em consideração a estrutura implícita, pois o número de comunidades é sempre fixo<ref>
{{cite journal
 | author = M. E. J. Newman
 | year = 2004
 | title = Detecting community structure in networks
 | journal = Eur. Phys. J. B
 | volume = 38
 | issue = 2
 | pages = 321–330
 | doi = 10.1140/epjb/e2004-00124-y
| bibcode = 2004EPJB...38..321N
 | hdl = 2027.42/43867
 }}
</ref>.

===Hierarchical clustering===

Outro método para encontrar estruturas comunitárias é [[agrupamento hierárquico]]. Nesse método, é necessário uma [[medida de similidade]] quantificando algum tipo de similidade (normalmente topológica) entre par de nós. Algumas medidas utilizadas são [[similaridade por cosseno]], [[índice de Jaccard]] e [[Distância de Hamming]] entre as linhas da matriz de adjacência. Então, são formadas as comunidades com nós similares levando em consideração essa métrica. Há diversos métodos para realizar o agrupamento desses nós, sendo um deles o [[clustering de ligação única]], no qual dois grupos são considerados separados em comunidades se e somente se todos os pares de nós em grupos diferentes tem a similaridade maior que um limiar. Outra abordagem que obteve resultados melhores é o uso de várias métricas de similaridades e dissimilaridades, combinadas através de uma [[Conjunto_convexo#Combinação convexa|combinação convexa]]<ref>{{cite journal
|title = Weighting dissimilarities to detect communities in networks
|journal = Phil. Trans. R. Soc. A
|date = 2015-12-13
|issn = 1364-503X
|pmid = 26527808
|pages = 20150108
|volume = 373
|issue = 2056
|doi = 10.1098/rsta.2015.0108
|first1 = Alejandro J.
|last1 = Alvarez
|first2 = Carlos E.
|last2 = Sanz-Rodríguez
|first3 = Juan Luis
|last3 = Cabrera
|bibcode = 2015RSPTA.37350108A
}}</ref>.

===Algoritmo de Girvan–Newman===

Outra abordagem para detecção de comunidades é o [[algoritmo de Girvan-Newman]]
<ref name=fast>
{{cite journal
 | author = M. E. J. Newman
 | year = 2004
 | title = Fast algorithm for detecting community structure in networks
 | journal = Phys. Rev. E
 | volume = 69
 | issue = 6
 | pages = 066133
 | doi = 10.1103/PhysRevE.69.066133
| pmid = 15244693
 | arxiv = cond-mat/0309508
 | bibcode = 2004PhRvE..69f6133N
 }}
</ref>. Esse algoritmo identifica as arestas em uma rede que estão na fronteira de comunidades e as remove, deixando somente as comunidades isoladas. A identificação é feita utilizando [[intermediação]], que é um número associado a cada aresta onde esse valor é maior se a aresta está "entre" muitos pares de nós.

O algoritmo de Girvan-Newman retorna resultados razoáveis em relação a qualidade mas sua popularidade advém do fato que esse método é implementado em diversos pacotes de software. Em contrapartida, sua execução é lenta levando tempo proporcional a <math>O(E^2 V)</math> em uma rede de <math>V</math> vértices e <math>E</math> arestas, por essa razão é impraticável para redes de alguns milhares de nós<ref name=fast/>.

===Maximização da modularidade===

Apesar de suas desvantagens, um dos métodos mais utilizados para detecção de comunidades é a [[Pontos_extremos_de_uma_função|maximização]] da [[Estrutura comunitária#modularidade|modularidade]]. A maximização da modularidade detecta comunidades realizando uma busca entre candidatos de partições e seleciona a partição (ou partições) com maior modularidade. Devido ao fato que uma busca por todas as possíveis partições é algo intratável, algoritmos baseados em [[Algoritmo de aproximação|aproximação]] são utilizados como [[Algoritmo guloso|algoritmos gulosos]], [[simulated annealing]], [[otimização espectral]]. Essas propostas oferecem diferentes resultados referente a velocidade e acurácia<ref name=DDD2005>
{{cite journal
 |author1=L. Danon |author2=J. Duch |author3=A. Díaz-Guilera |author4=A. Arenas | year = 2005
 | title = Comparing community structure identification
 | journal = J. Stat. Mech.
 | volume = 2005
 | issue = 9
 | pages = P09008
 | doi = 10.1088/1742-5468/2005/09/P09008
 |arxiv=cond-mat/0505245|bibcode=2005JSMTE..09..008D
}}
</ref><ref>
{{cite journal
 |author1=R. Guimera |author2=L. A. N. Amaral | year = 2005
 | title = Functional cartography of complex metabolic networks
 | journal = Nature
 | volume = 433
 | pages = 895–900
 | doi = 10.1038/nature03288
 | issue=7028
 | pmid=15729348
 | pmc=2175124
| arxiv=q-bio/0502035| bibcode=2005Natur.433..895G}}
</ref>. Um método popular de maximização da modularidade é o [[método de Louvain]], que iterativamente realiza a otimização de comunidades locais até que a modularidade global não seja mais melhorada através de perturbações na partição de comunidades<ref>
{{cite journal
 |author1=V.D. Blondel |author2=J.-L. Guillaume |author3=R. Lambiotte |author4=E. Lefebvre | year = 2008
 | title =  Fast unfolding of community hierarchies in large networks
 | journal = J. Stat. Mech.
 | volume = 2008
 | issue = 10
 | pages = P10008
 | doi = 10.1088/1742-5468/2008/10/P10008
 |arxiv=0803.0476|bibcode=2008JSMTE..10..008B
}}
</ref><ref>
{{cite techreport
|title=Lightning-fast Community Detection in Social Media: A Scalable Implementation of the Louvain Algorithm
|year=2013
|first1=Xinyu |last1=Que
|first2=Fabio |last2=Checconi
|first3=Fabrizio |last3=Petrini
|first4=Teng |last4=Wang
|first5=Weikuan |last5=Yu
|number=AU-CSSE-PASL/13-TR01
|institution=Computer Architecture and SysTems Research Lab (CASTL), Florida State University
}}</ref>. Atualmente, o melhor algoritmo para a otimização de modularidade utiliza o método RenELL que é um exemplo de [[aprendizado ensemble extremo]]<ref>
{{cite journal
 |author1=J. Guo |author2=P. Singh | author3=K.E. Bassler | year = 2019
 | title = Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
 | journal = Scientific Reports
 | volume = 9
 | doi = 10.1038/s41598-019-50739-3
 | issue = 14234
 |pages=14234 
 |pmid=31578406
 |pmc=6775136
 |arxiv=1909.10491
 |bibcode=2019NatSR...914234G 
 }}
</ref>
<ref name="RenEEL-Modularity">{{cite web
 |title=RenEEL-Modularity
 |date=11 de Janeiro de 2021
 |url=https://github.com/kbassler/RenEEL-Modularity
}}</ref>.

A modularidade é questionada como métrica para otimização porque já foi mostrado que sua maximização falha em detectar [[clusters]] menores que certa escala que depende do tamanho da rede<ref name=Fortunato2007>
{{cite journal
 |author1=S. Fortunato |author2=M. Barthelemy | year = 2007
 | title = Resolution limit in community detection
 | journal = Proceedings of the National Academy of Sciences of the United States of America
 | volume = 104
 | pages = 36–41
 | pmid = 17190818
 | doi = 10.1073/pnas.0605965104
 | issue = 1
 | pmc = 1765466
| arxiv = physics/0607100| bibcode = 2007PNAS..104...36F}}
</ref>.

<!-- —————— Fim!  —————— -->
{{referências}}

[[Categoria:!Artigos novos]]
[[Categoria:Redes]]
[[Categoria:Lógica matemática]]