An Approximation Algorithm for Active Friending in Online Social Networks Article Swipe
Guangmo Tong
,
Ruiqi Wang
,
Xiang Li
,
Weili Wu
,
Ding‐Zhu Du
·
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1811.00643
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1811.00643
Guiding users to actively expanding their online social circles is one of the primary strategies for enhancing user participation and growing online social networks. In this paper, we study the active friending problem which aims at providing users with the strategy for methodically sending invitations to successfully build a friendship with target users. We consider the prominent linear threshold model for the friending process and formulate the active friending problem as an optimization problem. The key observation is the relationship between the active friending problem and the minimum subset cover problem, based on which we present the first randomized algorithm with a data-independent approximation ratio and a controllable success probability for general graphs. The performance of the proposed algorithm is theoretically analyzed and supported by encouraging simulation results done on extensive datasets.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/1811.00643
- https://arxiv.org/pdf/1811.00643
- OA Status
- green
- References
- 22
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W2899190178
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2899190178Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.1811.00643Digital Object Identifier
- Title
-
An Approximation Algorithm for Active Friending in Online Social NetworksWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2018Year of publication
- Publication date
-
2018-11-01Full publication date if available
- Authors
-
Guangmo Tong, Ruiqi Wang, Xiang Li, Weili Wu, Ding‐Zhu DuList of authors in order
- Landing page
-
https://arxiv.org/abs/1811.00643Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/1811.00643Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/1811.00643Direct OA link when available
- Concepts
-
Computer science, Key (lock), Social network (sociolinguistics), Social media, World Wide Web, Computer securityTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
22Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2899190178 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.1811.00643 |
| ids.doi | https://doi.org/10.48550/arxiv.1811.00643 |
| ids.mag | 2899190178 |
| ids.openalex | https://openalex.org/W2899190178 |
| fwci | |
| type | preprint |
| title | An Approximation Algorithm for Active Friending in Online Social Networks |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10064 |
| topics[0].field.id | https://openalex.org/fields/31 |
| topics[0].field.display_name | Physics and Astronomy |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/3109 |
| topics[0].subfield.display_name | Statistical and Nonlinear Physics |
| topics[0].display_name | Complex Network Analysis Techniques |
| topics[1].id | https://openalex.org/T12592 |
| topics[1].field.id | https://openalex.org/fields/31 |
| topics[1].field.display_name | Physics and Astronomy |
| topics[1].score | 0.9973999857902527 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/3109 |
| topics[1].subfield.display_name | Statistical and Nonlinear Physics |
| topics[1].display_name | Opinion Dynamics and Social Influence |
| topics[2].id | https://openalex.org/T11704 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9876000285148621 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1706 |
| topics[2].subfield.display_name | Computer Science Applications |
| topics[2].display_name | Mobile Crowdsensing and Crowdsourcing |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.6523010730743408 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C26517878 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5605139136314392 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q228039 |
| concepts[1].display_name | Key (lock) |
| concepts[2].id | https://openalex.org/C4727928 |
| concepts[2].level | 3 |
| concepts[2].score | 0.48010018467903137 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q17164759 |
| concepts[2].display_name | Social network (sociolinguistics) |
| concepts[3].id | https://openalex.org/C518677369 |
| concepts[3].level | 2 |
| concepts[3].score | 0.4688488245010376 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q202833 |
| concepts[3].display_name | Social media |
| concepts[4].id | https://openalex.org/C136764020 |
| concepts[4].level | 1 |
| concepts[4].score | 0.23389413952827454 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q466 |
| concepts[4].display_name | World Wide Web |
| concepts[5].id | https://openalex.org/C38652104 |
| concepts[5].level | 1 |
| concepts[5].score | 0.09755584597587585 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3510521 |
| concepts[5].display_name | Computer security |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.6523010730743408 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/key |
| keywords[1].score | 0.5605139136314392 |
| keywords[1].display_name | Key (lock) |
| keywords[2].id | https://openalex.org/keywords/social-network |
| keywords[2].score | 0.48010018467903137 |
| keywords[2].display_name | Social network (sociolinguistics) |
| keywords[3].id | https://openalex.org/keywords/social-media |
| keywords[3].score | 0.4688488245010376 |
| keywords[3].display_name | Social media |
| keywords[4].id | https://openalex.org/keywords/world-wide-web |
| keywords[4].score | 0.23389413952827454 |
| keywords[4].display_name | World Wide Web |
| keywords[5].id | https://openalex.org/keywords/computer-security |
| keywords[5].score | 0.09755584597587585 |
| keywords[5].display_name | Computer security |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:1811.00643 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/1811.00643 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/1811.00643 |
| locations[1].id | doi:10.48550/arxiv.1811.00643 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.1811.00643 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5011783006 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-3247-4019 |
| authorships[0].author.display_name | Guangmo Tong |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I86501945 |
| authorships[0].affiliations[0].raw_affiliation_string | University of Delaware, USA |
| authorships[0].institutions[0].id | https://openalex.org/I86501945 |
| authorships[0].institutions[0].ror | https://ror.org/01sbq1a82 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I86501945 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | University of Delaware |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Guangmo Tong |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | University of Delaware, USA |
| authorships[1].author.id | https://openalex.org/A5100387946 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-4725-3892 |
| authorships[1].author.display_name | Ruiqi Wang |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I86501945 |
| authorships[1].affiliations[0].raw_affiliation_string | University of Delaware, USA |
| authorships[1].institutions[0].id | https://openalex.org/I86501945 |
| authorships[1].institutions[0].ror | https://ror.org/01sbq1a82 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I86501945 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | University of Delaware |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ruiqi Wang |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of Delaware, USA |
| authorships[2].author.id | https://openalex.org/A5100674281 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-6482-2535 |
| authorships[2].author.display_name | Xiang Li |
| authorships[2].countries | US |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I16269868 |
| authorships[2].affiliations[0].raw_affiliation_string | Santa Clara University, USA. |
| authorships[2].institutions[0].id | https://openalex.org/I16269868 |
| authorships[2].institutions[0].ror | https://ror.org/03ypqe447 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I16269868 |
| authorships[2].institutions[0].country_code | US |
| authorships[2].institutions[0].display_name | Santa Clara University |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Xiang Li |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Santa Clara University, USA. |
| authorships[3].author.id | https://openalex.org/A5070037321 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-8747-6340 |
| authorships[3].author.display_name | Weili Wu |
| authorships[3].affiliations[0].raw_affiliation_string | University of Texas at Dallas; USA |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Weili Wu |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | University of Texas at Dallas; USA |
| authorships[4].author.id | https://openalex.org/A5037860988 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-7345-2185 |
| authorships[4].author.display_name | Ding‐Zhu Du |
| authorships[4].affiliations[0].raw_affiliation_string | University of Texas at Dallas; USA |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Ding-Zhu Du |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | University of Texas at Dallas; USA |
| has_content.pdf | True |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/1811.00643 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2018-11-09T00:00:00 |
| display_name | An Approximation Algorithm for Active Friending in Online Social Networks |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10064 |
| primary_topic.field.id | https://openalex.org/fields/31 |
| primary_topic.field.display_name | Physics and Astronomy |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/3109 |
| primary_topic.subfield.display_name | Statistical and Nonlinear Physics |
| primary_topic.display_name | Complex Network Analysis Techniques |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626, https://openalex.org/W2120116197, https://openalex.org/W159653547 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:1811.00643 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/1811.00643 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/1811.00643 |
| primary_location.id | pmh:oai:arXiv.org:1811.00643 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/1811.00643 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/1811.00643 |
| publication_date | 2018-11-01 |
| publication_year | 2018 |
| referenced_works | https://openalex.org/W2962860893, https://openalex.org/W2396832258, https://openalex.org/W2028228423, https://openalex.org/W2755088640, https://openalex.org/W1980672078, https://openalex.org/W1995323604, https://openalex.org/W2114909350, https://openalex.org/W2963725737, https://openalex.org/W2140426283, https://openalex.org/W2136664839, https://openalex.org/W1990570693, https://openalex.org/W2773238158, https://openalex.org/W1996320586, https://openalex.org/W2061820396, https://openalex.org/W2395439732, https://openalex.org/W2963122331, https://openalex.org/W2106111489, https://openalex.org/W2533692962, https://openalex.org/W2034873408, https://openalex.org/W2083491675, https://openalex.org/W2914771567, https://openalex.org/W2108278206 |
| referenced_works_count | 22 |
| abstract_inverted_index.a | 48, 101, 106 |
| abstract_inverted_index.In | 24 |
| abstract_inverted_index.We | 53 |
| abstract_inverted_index.an | 71 |
| abstract_inverted_index.as | 70 |
| abstract_inverted_index.at | 35 |
| abstract_inverted_index.by | 124 |
| abstract_inverted_index.is | 9, 77, 119 |
| abstract_inverted_index.of | 11, 115 |
| abstract_inverted_index.on | 92, 129 |
| abstract_inverted_index.to | 2, 45 |
| abstract_inverted_index.we | 27, 94 |
| abstract_inverted_index.The | 74, 113 |
| abstract_inverted_index.and | 19, 64, 85, 105, 122 |
| abstract_inverted_index.for | 15, 41, 60, 110 |
| abstract_inverted_index.key | 75 |
| abstract_inverted_index.one | 10 |
| abstract_inverted_index.the | 12, 29, 39, 55, 61, 66, 78, 81, 86, 96, 116 |
| abstract_inverted_index.aims | 34 |
| abstract_inverted_index.done | 128 |
| abstract_inverted_index.this | 25 |
| abstract_inverted_index.user | 17 |
| abstract_inverted_index.with | 38, 50, 100 |
| abstract_inverted_index.based | 91 |
| abstract_inverted_index.build | 47 |
| abstract_inverted_index.cover | 89 |
| abstract_inverted_index.first | 97 |
| abstract_inverted_index.model | 59 |
| abstract_inverted_index.ratio | 104 |
| abstract_inverted_index.study | 28 |
| abstract_inverted_index.their | 5 |
| abstract_inverted_index.users | 1, 37 |
| abstract_inverted_index.which | 33, 93 |
| abstract_inverted_index.active | 30, 67, 82 |
| abstract_inverted_index.linear | 57 |
| abstract_inverted_index.online | 6, 21 |
| abstract_inverted_index.paper, | 26 |
| abstract_inverted_index.social | 7, 22 |
| abstract_inverted_index.subset | 88 |
| abstract_inverted_index.target | 51 |
| abstract_inverted_index.users. | 52 |
| abstract_inverted_index.Guiding | 0 |
| abstract_inverted_index.between | 80 |
| abstract_inverted_index.circles | 8 |
| abstract_inverted_index.general | 111 |
| abstract_inverted_index.graphs. | 112 |
| abstract_inverted_index.growing | 20 |
| abstract_inverted_index.minimum | 87 |
| abstract_inverted_index.present | 95 |
| abstract_inverted_index.primary | 13 |
| abstract_inverted_index.problem | 32, 69, 84 |
| abstract_inverted_index.process | 63 |
| abstract_inverted_index.results | 127 |
| abstract_inverted_index.sending | 43 |
| abstract_inverted_index.success | 108 |
| abstract_inverted_index.actively | 3 |
| abstract_inverted_index.analyzed | 121 |
| abstract_inverted_index.consider | 54 |
| abstract_inverted_index.problem, | 90 |
| abstract_inverted_index.problem. | 73 |
| abstract_inverted_index.proposed | 117 |
| abstract_inverted_index.strategy | 40 |
| abstract_inverted_index.algorithm | 99, 118 |
| abstract_inverted_index.datasets. | 131 |
| abstract_inverted_index.enhancing | 16 |
| abstract_inverted_index.expanding | 4 |
| abstract_inverted_index.extensive | 130 |
| abstract_inverted_index.formulate | 65 |
| abstract_inverted_index.friending | 31, 62, 68, 83 |
| abstract_inverted_index.networks. | 23 |
| abstract_inverted_index.prominent | 56 |
| abstract_inverted_index.providing | 36 |
| abstract_inverted_index.supported | 123 |
| abstract_inverted_index.threshold | 58 |
| abstract_inverted_index.friendship | 49 |
| abstract_inverted_index.randomized | 98 |
| abstract_inverted_index.simulation | 126 |
| abstract_inverted_index.strategies | 14 |
| abstract_inverted_index.encouraging | 125 |
| abstract_inverted_index.invitations | 44 |
| abstract_inverted_index.observation | 76 |
| abstract_inverted_index.performance | 114 |
| abstract_inverted_index.probability | 109 |
| abstract_inverted_index.controllable | 107 |
| abstract_inverted_index.methodically | 42 |
| abstract_inverted_index.optimization | 72 |
| abstract_inverted_index.relationship | 79 |
| abstract_inverted_index.successfully | 46 |
| abstract_inverted_index.approximation | 103 |
| abstract_inverted_index.participation | 18 |
| abstract_inverted_index.theoretically | 120 |
| abstract_inverted_index.data-independent | 102 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 5 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/10 |
| sustainable_development_goals[0].score | 0.49000000953674316 |
| sustainable_development_goals[0].display_name | Reduced inequalities |
| citation_normalized_percentile |