Graph Theory and Society

People interested in social networking use the term network for what computer scientists call a graph.  Combinatorial optimization is applied graph theory.  Most people think of a graph as something quite different, what is more correctly called a plot.  This website is about the application of graph theory to social networks, so it might be less misleading just to use the term network.  Therefore, the name of this website is Social Network Optimization.   Its purpose it to help find and promote genuine solutions to social problems.

Older solutions that are genuine enough, but too limited, include those discussed on the brief Social Algorithms page but such solutions are surprisingly restricted and ineffective in comparison to solutions based on combinatorial and graph theoretic methods. So currently the solutions receiving the most attention involve the creation of new social structure through the matching of individuals, organizations, and social contexts .

Many humanities and social sciences people, especially those interested in politics, and many ordinary people as well, have an apparent inability to believe that anything containing the word optimization could involve low-level interpersonal networking and be strictly consensual — they insist in looking for the controlling hand of the bureaucrat or capitalist. That is a complete misinterpretation, and so other names or expressions will be used.

The approach to social problems discussed here is based on the following observations:

  • the poorest people are those who lack social connections (jobs, family, friends) and the route away from poverty almost always involves making such connections
  • the most dangerous people are those whose social connections are poor or inappropriate (loners, gang members) and the only way such people stop being a threat to themselves and others is through better social contacts
  • the saddest and loneliest people are those with poor social connections (unmarried, few and poor friendships, etc.) and these are also the people most likely to commit suicide unless they gain such connections

Poverty, crime, and social disorder are all symptoms of social mismatch or the lack of social integration. For human society to survive and prosper almost everybody should be well integrated into society with suitable work to do and strong social relationships. To make that possible it should be easy to find productive work and to maintain viable communities based on strong interpersonal relationships.

  • It should be easy to find a good job, but it isn’t. It is even harder to find a truly suitable job which matches your abilities.
  • It should be easy to find a compatible spouse or sexual partner, but again, it isn’t. And it is much harder to find someone truly compatible where the attraction is mutual.
  • It should also be easy find close friends and make other important social connections, but even this is hard, and it is especially hard to make long-lasting friends.

All of this may soon change with the introduction of new social technology.

There are several goals or targets, which will eventually be written more formally as a requirements analysis document. Here are some of these goals:

  1. Privacy and Security — people may be reluctant to participate if their personality profile or other personal data is not keep secret. This information must also be kept secure against outside meddling — we can’t have people changing other people’s data.
  2. Theory-proof and Theory-correcting. This system should not depend on any particular theory of personality, and although some theories may be used for making initial estimates, the use of this system should bring in new information which can be used to correct the theoretical models.
  3. Easy to use. The system should be user-friendly and not require a lot of work from users up front. It should also be easy to upgrade personal information.
  4. Aid to self-awareness. Whether or not a particular user wants matching done, the data should be available as an aid to self-awareness.
  5. Fun. The system should be fun to play with.
  6. Any and all use of this must be entirely optional, with lots of chances to back away from involvment with the system, and in particular it should be very easy to ignore or back away from suggestions made by the system.
  7. The system must confine itself to suggestions, and these suggestions must be keep a secret from all but the interested people themselves.

More goals will be added. Now here are some design ideas and the further goals generated by and associated with them:

  1. Initially the user will be asked to fill out a questionaire.
    • Questions should be interesting.
    • It should be possible to play with the system, answering the questionaire several times with different answers, to see what happens.
    • Feedback should be immediate, or at least quick.
    • If possible an interactive system that shows personality and skill estimates as they change with each question answered
  2. The user should be able save answer sets, load them, modify them, and to submit them as an experiment or as real submission for use.
  3. The system should support several standard personality measures, such as Myers-Briggs, Cattell, Sheldon, and some skills or aptitude measures as well.
  4. For security users will be given a randomly chosen number or an alias they choose, or both, so that whoever is processing the data (me for the time being) will not know what data set represents what person.
    • This is not good enough for true privacy and security, so provisions to upgrade to a safer system should be made in advance.
    • Test questions should be chosen to reduce the possibility of abuse of data — e.g., though it would be nice to include birthdate information, that is too easy to misuse, so it can’t be used. No data that identifies the user should be collected.
  5. Matching suggestions should be made in a careful way using aliases or numbers (or both), with some kind of handshaking protocol to let people mutually identify each other after some preliminary exchanges of information. E.g. both user 57809 and 12744 may be told that the system has suggested a match for some purpose, then if that is acceptable, an anonymous meeting can be set up, and if that is successful the two can reveal themselves to each other.
    • matching for working-together-on-some-task is a high priority since we all have so much work to do
    • matching for the buddy system should be a high priority, because it is needed in Frontiers
    • matching for simple friendship is easy enough, I think
    • matching for more intimate connections is something many people want, but we have to be very careful about it — to be discussed elsewhere
    • matching for real world jobs is a future possibility, may need to be developed in cooperation with some employment agency

I have written about all this elsewhere, and will be writing more about it. This is just a draft, no, just the sketch of a draft.

The key thing that is different about this proposal is that I want to actually implement it, and I want people to start using it as soon as possible.

Implementation notes, with further goals and design ideas generated from and associated with them:

  1. The user interface will be a combination of HTML text and forms with a Java applet that will let the user answer questions and will show personality estimates in some graphical form — perhaps several forms, maybe a pie chart for Sheldon stuff, a table for Myers-Briggs, and a histogram for Cattell stuff.
  2. To make it interactive, the estimates should be based on Bayesian estimation with the estimates changing as each question is answered.
  3. For fun, the user should be able to play and fantasize, entering ficticious names like “Adolph” and trying to guess how Hitler would have answered the questions. It should also be possible to do matching in small ficticious populations, such as imagining an island with all sorts of notorious villans and heroes, and seeing who should have done what with whom.
  4. For real matching the system should keep for each user a best set of estimates — or for security it may be best to for each user to keep his or her own best estimates.
  5. Real matching suggestions for real people should be as tactful and carefully done as possible, which may involve making suggestion forms available for discussion and community design.
  6. As an initial theory we can (at least) use my own theory which matches people who have interests, some aesthetic tastes, and some knowledge in common but are otherwise as different as possible. Actually use of the system will fix problems with this or any other theory.
  7. For the actual combinatorial optimization steps there are several algorithms already implemented in C, Pascal, and Fortran that can easily be translated if need be. It is probably best to use at least:
    • an assignment problem problem algorithm, such as the Hungarian algorithm
    • a minimum-spanning-tree algorithm (I use Kruskal’s) in which people are connected in a(n unrooted) tree structure, with some people getting several matches (links), but at least one good match or link is provided for everybody.
  8. Two types of data should be collected after suggestions are made:
    • was the suggestion acceptable, was it acted upon
    • if acted upon, was it any good?
  9. The key idea is to use feedback to maximize the last two measures, so that the suggestions are more and more likely to be acted upon, and so that when acted upon they are better and better.

Leave a Reply

Your email address will not be published. Required fields are marked *