Journal Home > Volume 2 , Issue 4
Intelligent and Converged Networks 2021, 2(4): 306-319 https://doi.org/10.23919/ICN.2021.0022
Open Access | Issue | Published: 30 December 2021

Public-private-core maintenance in public-private-graphs

Show Author's Information Dongxiao Yu1,  Xilian Zhang1,  Qi Luo1( ),  Lifang Zhang1,  Zhenzhen Xie1,  Zhipeng Cai2
School of Computer Science and Technology, Shandong University, Qingdao 266200, China
Department of Computer Science, Georgia State University, Atlanta, GA 30080, USA
Keywords:
social network, core decomposition maintenance, public-private-graph (pp-graph), critical user
Cite this article:
Yu D, Zhang X, Luo Q, et al. Public-private-core maintenance in public-private-graphs. Intelligent and Converged Networks, 2021, 2(4): 306-319. https://doi.org/10.23919/ICN.2021.0022
Download citation
EndNote(RIS)
BibTeX

644

Views

56

Downloads

Citations

0

Crossref

N/A

WoS

0

Scopus

N/A

CSCD

Abstract Full text About this article

A public-private-graph (pp-graph) is developed to model social networks with hidden relationships, and it consists of one public graph in which edges are visible to all users, and multiple private graphs in which edges are only visible to its endpoint users. In contrast with conventional graphs where the edges can be visible to all users, it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph. In this paper, we first propose a novel concept, public-private-core (pp-core) number based on the k-core number, which integrally considers both the public graph and private graphs of vertices, to measure how critical a user is. We then give an efficient algorithm for the pp-core number computation, which takes only linear time and space. Considering that the graphs can be always evolving over time, we also present effective algorithms for pp-core maintenance after the graph changes, avoiding redundant re-computation of pp-core number. Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability. Compared to recalculating the pp-core numbers of all vertices, our maintenance algorithms can reduce the computation time by about 6–8 orders of magnitude.


menu
Abstract
Full text
Outline
About this article

Public-private-core maintenance in public-private-graphs

Show Author's information Dongxiao Yu1, Xilian Zhang1, Qi Luo1( ), Lifang Zhang1, Zhenzhen Xie1, Zhipeng Cai2
School of Computer Science and Technology, Shandong University, Qingdao 266200, China
Department of Computer Science, Georgia State University, Atlanta, GA 30080, USA

Abstract

A public-private-graph (pp-graph) is developed to model social networks with hidden relationships, and it consists of one public graph in which edges are visible to all users, and multiple private graphs in which edges are only visible to its endpoint users. In contrast with conventional graphs where the edges can be visible to all users, it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph. In this paper, we first propose a novel concept, public-private-core (pp-core) number based on the k-core number, which integrally considers both the public graph and private graphs of vertices, to measure how critical a user is. We then give an efficient algorithm for the pp-core number computation, which takes only linear time and space. Considering that the graphs can be always evolving over time, we also present effective algorithms for pp-core maintenance after the graph changes, avoiding redundant re-computation of pp-core number. Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability. Compared to recalculating the pp-core numbers of all vertices, our maintenance algorithms can reduce the computation time by about 6–8 orders of magnitude.

Keywords: social network, core decomposition maintenance, public-private-graph (pp-graph), critical user

References(29)

1
R. Dey, Z. Jelveh, and K. Ross, Facebook users have become much more private: A large-scale study, in Proc. 2012 IEEE Int. Conf. on Pervasive Computing and Communications Workshops, Lugano, Switzerland, 2012, pp. 346−352.https://doi.org/10.1109/PerComW.2012.6197508
DOI
2
F. Chierichetti, A. Epasto, R. Kumar, S. Lattanzi, and V. Mirrokni, Efficient algorithms for public-private social networks, in Proc. 21thACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 139−148.https://doi.org/10.1145/2783258.2783354
DOI
3
A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy, A sketch-based distance oracle for web-scale graphs, in Proc. 3rdACM Int. Conf. on Web Search and Data Mining, New York, NY, USA, 2010, pp. 401−410.https://doi.org/10.1145/1718487.1718537
DOI
4
T. H. Haveliwala, Topic-sensitive PageRank, in Proc. 11thInt. Conf. on World Wide Web, Honolulu, HI, USA, 2002, pp. 517−526.https://doi.org/10.1145/511446.511513
DOI
5

N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn., vol. 56, nos. 1–3, pp. 89–113, 2004.
DOI Google Scholar
6

K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma, Preventing unraveling in social networks: The anchored k-core problem, SIAM J. Discrete Math., vol. 29, no. 3, pp. 1452–1475, 2015.
DOI Google Scholar
7

F. Zhang, W. J. Zhang, Y. Zhang, L. Qin, and X. M. Lin, OLAK: An efficient algorithm to prevent unraveling in social networks, Proc. VLDB Endow., vol. 10, no. 6, pp. 649–660, 2017.
DOI Google Scholar
8
F. Zhang, Y. Zhang, L. Qin, W. J. Zhang, and X. M. Lin, Finding critical users for social network engagement: The collapsed k-core problem, in Proc. 31stAAAI Conf. on Artificial Intelligence, San Francisco, CA, USA, 2017, pp. 245−251.
9

F. Zhang, C. G. Li, Y. Zhang, L. Qin, and W. J. Zhang, Finding critical users in social communities: The collapsed core and truss problems, IEEE Trans. Knowl. Data Eng., vol. 32, no. 1, pp. 78–91, 2020.
DOI Google Scholar
10
S. B. Seidman, Network structure and minimum degree, Soc. Netw. , vol. 5, no. 3, pp. 269−287, 1983.https://doi.org/10.1016/0378-8733(83)90028-X
DOI
11

Q. S. Hua, Y. L. Shi, D. X. Yu, H. Jin, J. G. Yu, Z. P. Cai, X. Z. Cheng, and H. H. Chen, Faster parallel core maintenance algorithms in dynamic graphs, IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 6, pp. 1287–1300, 2020.
DOI Google Scholar
12
V. Batagelj and M. Zaversnik, An O(m) algorithm for cores decomposition of networks, arXiv preprint arXiv: cs/0310049, 2003.
13
V. Batagelj and M. Zaveršnik, Fast algorithms for determining (generalized) core groups in social networks,Adv. Data Anal. Classi. , vol. 5, no. 2, pp. 129−145, 2011.https://doi.org/10.1007/s11634-010-0079-y
DOI
14

A. E. Saríyüce, B. Gedik, G. Jacques-Silva, K. L. Wu, and Ü. V. Çatalyürek, Streaming algorithms for k-core decomposition, Proc. VLDB Endow., vol. 6, no. 6, pp. 433–444, 2013.
DOI Google Scholar
15

M. A. Beauchamp, An improved index of centrality, Behav. Sci., vol. 10, no. 2, pp. 161–163, 1965.
DOI Google Scholar
16

P. Bonacich, Power and centrality: A family of measures, Am. J. Sociol., vol. 92, no. 5, pp. 1170–1182, 1987.
DOI Google Scholar
17
U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol. , vol. 25, no. 2, pp. 163−177, 2001.https://doi.org/10.1080/0022250X.2001.9990249
DOI
18
L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry, vol. 40, no. 1, pp. 35−41, 1977.https://doi.org/10.2307/3033543
DOI
19
Q. Luo, D. X. Yu, H. Sheng, J. G. Yu, and X. Z. Cheng, Distributed algorithm for truss maintenance in dynamic graphs, in Proc. 21stInt. Conf. on Parallel and Distributed Computing, Applications and Technologies, Shenzhen, China, 2021, pp. 104−115.https://doi.org/10.1007/978-3-030-69244-5_9
DOI
20
X. Huang, J. Jiang, B. Choi, J. Xu, Z. Zhang, and Y. Song, PP-DBLP: Modeling and generating attributed public-private networks with DBLP, in 2018 IEEE International Conference on Data Mining Workshops (ICDMW), doi: 10.1109/ICDMW.2018.00142.https://doi.org/10.1109/ICDMW.2018.00142
DOI
21
B. Mirzasoleiman, M. Zadimoghaddam, and A. Karbasi, Fast distributed submodular cover: Public-private data summarization, in Proc. 30thInt. Conf. on Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 3601−3609.
22
A. Archer, S. Lattanzi, P. Likarish, and S. Vassilvitskii, Indexing public-private graphs, in Proc. 26thInt. Conf. on World Wide Web, Perth, Australia, 2017, pp. 1461−1470.https://doi.org/10.1145/3038912.3052683
DOI
23
J. X. Jiang, X. Huang, B. Choi, J. L. Xu, S. S. Bhowmick, and L. Xu, PPKWS: An efficient framework for keyword search on public-private networks, in Proc. 36thInt. Conf. on Data Engineering(ICDE), Dallas, TX, USA, 2020, pp. 457−468.https://doi.org/10.1109/ICDE48307.2020.00046
DOI
24
J. Cheng, Y. P. Ke, S. M. Chu, and M. T. Özsu, Efficient core decomposition in massive networks, in Proc. 27thInt. Conf. on Data Engineering, Hannover, Germany, 2011, pp. 51−62.https://doi.org/10.1109/ICDE.2011.5767911
DOI
25

R. H. Li, J. X. Yu, and R. Mao, Efficient core maintenance in large dynamic graphs, IEEE Trans. Knowl. Data Eng., vol. 26, no. 10, pp. 2453–2465, 2014.
DOI Google Scholar
26
N. Dasari, D. Ranjan, and M. Zubair, ParK: An efficient algorithm for k-core decomposition on multicore processors, in Proc. 2014 IEEE Int. Conf. on Big Data (Big Data), Washington, DC, USA, 2014, pp. 9−16.https://doi.org/10.1109/BigData.2014.7004366
DOI
27
Q. Luo, D. X. Yu, F. Li, Z. H. Dou, Z. P. Cai, J. G. Yu, and X. Z. Cheng, Distributed core decomposition in probabilistic graphs, in Proc. 8thInt. Conf. on Computational Data and Social Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16−32.https://doi.org/10.1007/978-3-030-34980-6_2
DOI
28
W. Bai, Y. X. Zhang, X. Z. Liu, M. Chen, and D. Wu, Efficient core maintenance of dynamic graphs, in Proc. 25thInt. Conf. on Database Systems for Advanced Applications, Jeju, Republic of Korea, 2020, pp. 658−665.https://doi.org/10.1007/978-3-030-59416-9_42
DOI
29
D. X. Yu, N. Wang, Q. Luo, F. Li, J. G. Yu, X. Z. Cheng, and Z. P. Cai, Fast core maintenance in dynamic graphs, IEEE Trans. Comput. Soc. Syst., doi: 10.1109/TCSS.2021.3064836.https://doi.org/10.1109/TCSS.2021.3064836
DOI
Publication history
Copyright
Rights and permissions

Publication history

Received: 03 December 2021
Accepted: 18 January 2022
Published: 30 December 2021
Issue date: December 2021

Copyright

© All articles included in the journal are copyrighted to the ITU and TUP.

Rights and permissions

This work is available under the CC BY-NC-ND 3.0 IGO license: https://creativecommons.org/licenses/by-nc-nd/3.0/igo/

Return