Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Friendships and Close Friendships01:20

Friendships and Close Friendships

299
Friendship formation is a dynamic process shaped by psychological, cultural, and social factors. Friendships play a crucial role in emotional well-being, social development, and personal identity from childhood to adulthood.Childhood and Early FriendshipsFriendships in childhood often arise due to shared environments, such as school or neighborhood interactions. At this stage, proximity and common interests serve as the primary basis for connection. As children grow, their friendships evolve...
299
Robbers Cave04:49

Robbers Cave

15.1K
During the 1950s, the landmark Robbers Cave experiment demonstrated that when groups must compete with one another, intergroup conflict, hostility, and even violence may result. At the Oklahoman summer camp, two troops of boys—termed the Rattlers and the Eagles—took part in a week-long tournament. During this time, their negativity culminated in derogatory name-calling, fistfights, and even vandalism and destruction of property. However, this work also revealed that such tension...
15.1K
Factors Influencing Attraction I: Proximity01:22

Factors Influencing Attraction I: Proximity

389
Proximity plays a fundamental role in shaping interpersonal attraction by increasing opportunities for interaction and fostering familiarity. Research consistently demonstrates that individuals are more likely to form social bonds with those who are physically closer to them, whether in residential settings, workplaces, or educational institutions. This effect is largely driven by the increased frequency of encounters, which facilitates the development of friendships and romantic...
389
Relationship Formation02:12

Relationship Formation

46.3K
What do you think is the single most influential factor in determining with whom you become friends and whom you form romantic relationships? You might be surprised to learn that the answer is simple: the people with whom you have the most contact. This most important factor is proximity. You are more likely to be friends with people you have regular contact with. For example, there are decades of research that shows that you are more likely to become friends with people who live in your dorm,...
46.3K
Relationship Growth01:27

Relationship Growth

294
Interpersonal relationships progress through stages, beginning with awareness and moving toward mutuality, where emotional connections deepen. While many relationships remain at moderate levels of mutuality, deeper connections form through self-disclosure, trust, and interdependence.Self-DisclosureSelf-disclosure involves revealing personal information, starting with surface-level details and gradually progressing to more intimate content. As trust grows, individuals feel more comfortable...
294
In- and Out-Groups01:31

In- and Out-Groups

44.1K
People all belong to a gender, race, age, and social economic group. These groups provide a powerful source of our identity and self-esteem (Tajfel & Turner, 1979) and serve as our in-groups. An in-group is a group that we identify with or see ourselves as belonging to.
44.1K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same authorSame journal

On Polynomial Recursive Sequences.

Theory of computing systems·2024
Same author

Dynamic Data Structures for Timed Automata Acceptance.

Algorithmica·2022
Same author

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Algorithmica·2021
Same author

Applying deep learning to right whale photo identification.

Conservation biology : the journal of the Society for Conservation Biology·2018
Same author

Parameterized Complexity of Eulerian Deletion Problems.

Algorithmica·2014

Related Experiment Video

Updated: Apr 5, 2026

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy
07:53

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy

Published on: August 5, 2022

2.6K

Sitting Closer to Friends than Enemies, Revisited.

Marek Cygan1, Marcin Pilipczuk1, Michał Pilipczuk2

  • 1Institute of Informatics, University of Warsaw, Warsaw, Poland.

Theory of Computing Systems
|August 25, 2015
PubMed
Summary

This study investigates visualizing signed graphs, used in social networks. It proves the general problem of embedding signed graphs is NP-complete, providing complexity bounds.

Keywords:
Embedding into metric spaceRelationshipsSigned graphs

More Related Videos

Functional Near-Infrared Spectroscopy Hyperscanning Study in Psychological Counseling
06:04

Functional Near-Infrared Spectroscopy Hyperscanning Study in Psychological Counseling

Published on: January 17, 2025

1.8K
Peering into the Dynamics of Social Interactions: Measuring Play Fighting in Rats
15:01

Peering into the Dynamics of Social Interactions: Measuring Play Fighting in Rats

Published on: January 18, 2013

16.0K

Related Experiment Videos

Last Updated: Apr 5, 2026

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy
07:53

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy

Published on: August 5, 2022

2.6K
Functional Near-Infrared Spectroscopy Hyperscanning Study in Psychological Counseling
06:04

Functional Near-Infrared Spectroscopy Hyperscanning Study in Psychological Counseling

Published on: January 17, 2025

1.8K
Peering into the Dynamics of Social Interactions: Measuring Play Fighting in Rats
15:01

Peering into the Dynamics of Social Interactions: Measuring Play Fighting in Rats

Published on: January 18, 2013

16.0K

Area of Science:

  • Graph theory
  • Network visualization
  • Computational complexity

Background:

  • Signed graphs model relationships in social networks with positive (friends) and negative (enemies) edges.
  • Kermarrec and Thraves (2011) introduced the problem of embedding signed graphs into a metric space such that friends are closer than enemies.

Purpose of the Study:

  • To further investigate the embeddability of signed graphs into the metric space [Formula: see text].
  • To answer open questions posed by Kermarrec and Thraves regarding signed graph visualization.
  • To determine the computational complexity of the general signed graph embeddability problem.

Main Methods:

  • Relating embeddability of complete signed graphs to the recognition of proper interval graphs.
  • Proving the NP-completeness of the general signed graph embeddability problem.
  • Establishing lower and upper bounds for the time complexity of the general case.

Main Results:

  • The embeddability problem for complete signed graphs is linked to proper interval graph recognition.
  • The general signed graph embeddability problem is proven to be NP-complete.
  • A subexponential time algorithm for the general case would violate the Exponential Time Hypothesis.
  • A dynamic programming approach yields a single-exponential time complexity.

Conclusions:

  • The study provides a comprehensive analysis of signed graph embeddability.
  • The NP-completeness result clarifies the computational difficulty of visualizing signed networks.
  • The established complexity bounds offer insights into the practical feasibility of solving this problem.