An optimized MBE algorithm on sparse bipartite graphs

Yu He; Ronghua Li; Rui Mao

doi:10.1007/978-3-030-05755-8_21

An optimized MBE algorithm on sparse bipartite graphs

Yu He^*, Ronghua Li, Rui Mao

^*Corresponding author for this work

Shenzhen University

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

1 Citation (Scopus)

Abstract

The maximal biclique enumeration (MBE) is a problem of identifying all maximal bicliques in a bipartite graph. Once enumerated in a bipartite graph, maximal bicliques can be used to solve problems in areas such as purchase prediction, statistic analysis of social networks, discovery of interesting structures in protein-protein interaction networks, identification of common gene-set associations, and integration of diverse functional genomes data. In this paper, we develop an optimized sequential MBE algorithm called sMBEA for sparse bipartite graphs which appear frequently in real life. The results of extensive experiments on several real-life data sets demonstrate that sMBEA outperforms the state-of-the-art sequential algorithm iMBEA.

Original language	English
Title of host publication	Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings
Editors	Meikang Qiu
Publisher	Springer Verlag
Pages	206-216
Number of pages	11
ISBN (Print)	9783030057541
DOIs	https://doi.org/10.1007/978-3-030-05755-8_21
Publication status	Published - 2018
Externally published	Yes
Event	3rd International Conference on Smart Computing and Communications, SmartCom 2018 - Tokyo, Japan Duration: 10 Dec 2018 → 12 Dec 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11344 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Smart Computing and Communications, SmartCom 2018
Country/Territory	Japan
City	Tokyo
Period	10/12/18 → 12/12/18

Keywords

Biclique enumeration
Sparse bipartite graphs

Access to Document

10.1007/978-3-030-05755-8_21

Cite this

He, Y., Li, R., & Mao, R. (2018). An optimized MBE algorithm on sparse bipartite graphs. In M. Qiu (Ed.), Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings (pp. 206-216). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11344 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-05755-8_21

He, Yu ; Li, Ronghua ; Mao, Rui. / An optimized MBE algorithm on sparse bipartite graphs. Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings. editor / Meikang Qiu. Springer Verlag, 2018. pp. 206-216 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e3c2b129ff62477fa6a0289b80d2dab0,

title = "An optimized MBE algorithm on sparse bipartite graphs",

abstract = "The maximal biclique enumeration (MBE) is a problem of identifying all maximal bicliques in a bipartite graph. Once enumerated in a bipartite graph, maximal bicliques can be used to solve problems in areas such as purchase prediction, statistic analysis of social networks, discovery of interesting structures in protein-protein interaction networks, identification of common gene-set associations, and integration of diverse functional genomes data. In this paper, we develop an optimized sequential MBE algorithm called sMBEA for sparse bipartite graphs which appear frequently in real life. The results of extensive experiments on several real-life data sets demonstrate that sMBEA outperforms the state-of-the-art sequential algorithm iMBEA.",

keywords = "Biclique enumeration, Sparse bipartite graphs",

author = "Yu He and Ronghua Li and Rui Mao",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 3rd International Conference on Smart Computing and Communications, SmartCom 2018 ; Conference date: 10-12-2018 Through 12-12-2018",

year = "2018",

doi = "10.1007/978-3-030-05755-8_21",

language = "English",

isbn = "9783030057541",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "206--216",

editor = "Meikang Qiu",

booktitle = "Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings",

address = "Germany",

}

He, Y, Li, R & Mao, R 2018, An optimized MBE algorithm on sparse bipartite graphs. in M Qiu (ed.), Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11344 LNCS, Springer Verlag, pp. 206-216, 3rd International Conference on Smart Computing and Communications, SmartCom 2018, Tokyo, Japan, 10/12/18. https://doi.org/10.1007/978-3-030-05755-8_21

An optimized MBE algorithm on sparse bipartite graphs. / He, Yu; Li, Ronghua; Mao, Rui.
Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings. ed. / Meikang Qiu. Springer Verlag, 2018. p. 206-216 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11344 LNCS).

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

TY - GEN

T1 - An optimized MBE algorithm on sparse bipartite graphs

AU - He, Yu

AU - Li, Ronghua

AU - Mao, Rui

PY - 2018

Y1 - 2018

N2 - The maximal biclique enumeration (MBE) is a problem of identifying all maximal bicliques in a bipartite graph. Once enumerated in a bipartite graph, maximal bicliques can be used to solve problems in areas such as purchase prediction, statistic analysis of social networks, discovery of interesting structures in protein-protein interaction networks, identification of common gene-set associations, and integration of diverse functional genomes data. In this paper, we develop an optimized sequential MBE algorithm called sMBEA for sparse bipartite graphs which appear frequently in real life. The results of extensive experiments on several real-life data sets demonstrate that sMBEA outperforms the state-of-the-art sequential algorithm iMBEA.

AB - The maximal biclique enumeration (MBE) is a problem of identifying all maximal bicliques in a bipartite graph. Once enumerated in a bipartite graph, maximal bicliques can be used to solve problems in areas such as purchase prediction, statistic analysis of social networks, discovery of interesting structures in protein-protein interaction networks, identification of common gene-set associations, and integration of diverse functional genomes data. In this paper, we develop an optimized sequential MBE algorithm called sMBEA for sparse bipartite graphs which appear frequently in real life. The results of extensive experiments on several real-life data sets demonstrate that sMBEA outperforms the state-of-the-art sequential algorithm iMBEA.

KW - Biclique enumeration

KW - Sparse bipartite graphs

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

U2 - 10.1007/978-3-030-05755-8_21

DO - 10.1007/978-3-030-05755-8_21

M3 - Conference contribution

AN - SCOPUS:85058551905

SN - 9783030057541

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 206

EP - 216

BT - Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings

A2 - Qiu, Meikang

PB - Springer Verlag

T2 - 3rd International Conference on Smart Computing and Communications, SmartCom 2018

Y2 - 10 December 2018 through 12 December 2018

ER -

He Y, Li R, Mao R. An optimized MBE algorithm on sparse bipartite graphs. In Qiu M, editor, Smart Computing and Communication - 3rd International Conference, SmartCom 2018, Proceedings. Springer Verlag. 2018. p. 206-216. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-05755-8_21

An optimized MBE algorithm on sparse bipartite graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this