AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Intelligent and Converged Networks Article
PDF (8.9 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

School of Computer Science and Technology, Shandong University, Qingdao 266200, China
Department of Computer Science, Georgia State University, Atlanta, GA 30080, USA
Show Author Information

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 networkcore decomposition maintenancepublic-private-graph (pp-graph)critical user

References

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
Crossref
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
Crossref
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
Crossref
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
Crossref
5

N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn., vol. 56, nos. 1–3, pp. 89–113, 2004.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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
Crossref
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.
Crossref 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
Crossref
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.
Crossref Google Scholar
15

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

P. Bonacich, Power and centrality: A family of measures, Am. J. Sociol., vol. 92, no. 5, pp. 1170–1182, 1987.
Crossref 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
Crossref
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
Crossref
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
Crossref
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
Crossref
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
Crossref
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
Crossref
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
Crossref
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.
Crossref 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
Crossref
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
Crossref
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
Crossref
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
Crossref
Intelligent and Converged Networks
Volume 2 Issue 4,
December 2021
Pages 306-319
DOI: 10.23919/ICN.2021.0022
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

799

Views

58

Downloads

1

Crossref

1

Scopus

Altmetrics
Received: 03 December 2021
Accepted: 18 January 2022
Published: 30 December 2021
© All articles included in the journal are copyrighted to the ITU and TUP.

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