On finding socially tenuous groups for online social networks

Chih Ya Shen; Liang Hao Huang; De Nian Yang; Hong Han Shuai; Wang Chien Lee; Ming Syan Chen

doi:10.1145/3097983.3097995

On finding socially tenuous groups for online social networks

Chih Ya Shen, Liang Hao Huang, De Nian Yang, Hong Han Shuai, Wang Chien Lee, Ming Syan Chen

Computer Science and Engineering

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

21 Scopus citations

Abstract

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph-theoretical approaches for solving MkTG on general graphs effectively and efficiently Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.

Original language	English (US)
Title of host publication	KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	415-424
Number of pages	10
ISBN (Electronic)	9781450348874
DOIs	https://doi.org/10.1145/3097983.3097995
State	Published - Aug 13 2017
Event	23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017 - Halifax, Canada Duration: Aug 13 2017 → Aug 17 2017

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	Part F129685

Other

Other	23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017
Country/Territory	Canada
City	Halifax
Period	8/13/17 → 8/17/17

All Science Journal Classification (ASJC) codes

Software
Information Systems

Access to Document

10.1145/3097983.3097995

Cite this

Shen, C. Y., Huang, L. H., Yang, D. N., Shuai, H. H., Lee, W. C., & Chen, M. S. (2017). On finding socially tenuous groups for online social networks. In KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 415-424). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F129685). Association for Computing Machinery. https://doi.org/10.1145/3097983.3097995

Shen, Chih Ya ; Huang, Liang Hao ; Yang, De Nian et al. / On finding socially tenuous groups for online social networks. KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2017. pp. 415-424 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{e9b5316c1f91473fb2a9beae2e628c81,

title = "On finding socially tenuous groups for online social networks",

abstract = "Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph-theoretical approaches for solving MkTG on general graphs effectively and efficiently Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.",

author = "Shen, {Chih Ya} and Huang, {Liang Hao} and Yang, {De Nian} and Shuai, {Hong Han} and Lee, {Wang Chien} and Chen, {Ming Syan}",

note = "Publisher Copyright: {\textcopyright} 2017 ACM.; 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017 ; Conference date: 13-08-2017 Through 17-08-2017",

year = "2017",

month = aug,

day = "13",

doi = "10.1145/3097983.3097995",

language = "English (US)",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "415--424",

booktitle = "KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

}

Shen, CY, Huang, LH, Yang, DN, Shuai, HH, Lee, WC & Chen, MS 2017, On finding socially tenuous groups for online social networks. in KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. Part F129685, Association for Computing Machinery, pp. 415-424, 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017, Halifax, Canada, 8/13/17. https://doi.org/10.1145/3097983.3097995

On finding socially tenuous groups for online social networks. / Shen, Chih Ya; Huang, Liang Hao; Yang, De Nian et al.
KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2017. p. 415-424 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F129685).

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

TY - GEN

T1 - On finding socially tenuous groups for online social networks

AU - Shen, Chih Ya

AU - Huang, Liang Hao

AU - Yang, De Nian

AU - Shuai, Hong Han

AU - Lee, Wang Chien

AU - Chen, Ming Syan

PY - 2017/8/13

Y1 - 2017/8/13

N2 - Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph-theoretical approaches for solving MkTG on general graphs effectively and efficiently Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.

AB - Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph-theoretical approaches for solving MkTG on general graphs effectively and efficiently Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.

UR - http://www.scopus.com/inward/record.url?scp=85029056980&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029056980&partnerID=8YFLogxK

U2 - 10.1145/3097983.3097995

DO - 10.1145/3097983.3097995

M3 - Conference contribution

AN - SCOPUS:85029056980

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 415

EP - 424

BT - KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017

Y2 - 13 August 2017 through 17 August 2017

ER -

Shen CY, Huang LH, Yang DN, Shuai HH, Lee WC, Chen MS. On finding socially tenuous groups for online social networks. In KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2017. p. 415-424. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/3097983.3097995

On finding socially tenuous groups for online social networks

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this