New insight into 2-community structures in graphs with applications in social networks

Cristina Bazgan; Janka Chlebikova; Thomas  Pontoizeau

doi:10.1007/978-3-319-26626-8_18

New insight into 2-community structures in graphs with applications in social networks

Cristina Bazgan, Janka Chlebikova, Thomas Pontoizeau

School of Computing

Universite Paris Dauphine

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

120 Downloads (Pure)

Abstract

We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [A general view on computing communities, Mathematical Social Sciences 66(3):331--336, 2013]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs even
with additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings
Editors	Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, Ding-Zhu Du
Publisher	Springer
Chapter	18
Pages	236-250
Number of pages	15
ISBN (Electronic)	978-3-319-26626-8
ISBN (Print)	978-3-319-26625-1
DOIs	https://doi.org/10.1007/978-3-319-26626-8_18
Publication status	Published - 9 Dec 2015
Event	The 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015) - Texas, Houston, United States Duration: 18 Dec 2015 → 20 Dec 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9486
ISSN (Print)	0302-9743

Conference

Conference	The 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015)
Country/Territory	United States
City	Houston
Period	18/12/15 → 20/12/15

Keywords

graph theory
complexity theory
graph partitioning
community structure
clustering
social networks

Access to Document

10.1007/978-3-319-26626-8_18

New insight post-print
The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-319-26626-8_18.
Accepted author manuscript (Post-print), 172 KB

Cite this

Bazgan, C., Chlebikova, J., & Pontoizeau, T. (2015). New insight into 2-community structures in graphs with applications in social networks. In Z. Lu, D. Kim, W. Wu, W. Li, & D.-Z. Du (Eds.), Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings (pp. 236-250). (Lecture Notes in Computer Science; Vol. 9486). Springer. https://doi.org/10.1007/978-3-319-26626-8_18

Bazgan, Cristina ; Chlebikova, Janka ; Pontoizeau, Thomas . / New insight into 2-community structures in graphs with applications in social networks. Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings. editor / Zaixin Lu ; Donghyun Kim ; Weili Wu ; Wei Li ; Ding-Zhu Du. Springer, 2015. pp. 236-250 (Lecture Notes in Computer Science).

@inproceedings{46b51dc6b06e46acab3d2e55313165ef,

title = "New insight into 2-community structures in graphs with applications in social networks",

abstract = "We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [A general view on computing communities, Mathematical Social Sciences 66(3):331--336, 2013]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs evenwith additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.",

keywords = "graph theory, complexity theory, graph partitioning, community structure, clustering, social networks",

author = "Cristina Bazgan and Janka Chlebikova and Thomas Pontoizeau",

year = "2015",

month = dec,

day = "9",

doi = "10.1007/978-3-319-26626-8_18",

language = "English",

isbn = "978-3-319-26625-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "236--250",

editor = "Zaixin Lu and Donghyun Kim and Weili Wu and Wei Li and Ding-Zhu Du",

booktitle = "Combinatorial Optimization and Applications",

note = "The 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015) ; Conference date: 18-12-2015 Through 20-12-2015",

}

Bazgan, C, Chlebikova, J & Pontoizeau, T 2015, New insight into 2-community structures in graphs with applications in social networks. in Z Lu, D Kim, W Wu, W Li & D-Z Du (eds), Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9486, Springer, pp. 236-250, The 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015), Houston, United States, 18/12/15. https://doi.org/10.1007/978-3-319-26626-8_18

New insight into 2-community structures in graphs with applications in social networks. / Bazgan, Cristina; Chlebikova, Janka; Pontoizeau, Thomas .
Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings. ed. / Zaixin Lu; Donghyun Kim; Weili Wu; Wei Li; Ding-Zhu Du. Springer, 2015. p. 236-250 (Lecture Notes in Computer Science; Vol. 9486).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - New insight into 2-community structures in graphs with applications in social networks

AU - Bazgan, Cristina

AU - Chlebikova, Janka

AU - Pontoizeau, Thomas

PY - 2015/12/9

Y1 - 2015/12/9

N2 - We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [A general view on computing communities, Mathematical Social Sciences 66(3):331--336, 2013]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs evenwith additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.

AB - We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [A general view on computing communities, Mathematical Social Sciences 66(3):331--336, 2013]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs evenwith additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.

KW - graph theory

KW - complexity theory

KW - graph partitioning

KW - community structure

KW - clustering

KW - social networks

U2 - 10.1007/978-3-319-26626-8_18

DO - 10.1007/978-3-319-26626-8_18

M3 - Conference contribution

SN - 978-3-319-26625-1

T3 - Lecture Notes in Computer Science

SP - 236

EP - 250

BT - Combinatorial Optimization and Applications

A2 - Lu, Zaixin

A2 - Kim, Donghyun

A2 - Wu, Weili

A2 - Li, Wei

A2 - Du, Ding-Zhu

PB - Springer

T2 - The 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015)

Y2 - 18 December 2015 through 20 December 2015

ER -

Bazgan C, Chlebikova J, Pontoizeau T. New insight into 2-community structures in graphs with applications in social networks. In Lu Z, Kim D, Wu W, Li W, Du DZ, editors, Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings. Springer. 2015. p. 236-250. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-26626-8_18

New insight into 2-community structures in graphs with applications in social networks

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this