COLLABORATIVE TASK SCHEDULING METHOD BASEDON SOCIAL NETWORK ANALYSIS FOR CELLPHONEAPPLICATION
Ikki Ohmukai
The Graduate University for Advanced Studies
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japani2k@grad.nii.ac.jp

Hideaki Takeda
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
takeda@nii.ac.jp

ABSTRACTThis paper proposes a collaborative approach for personal task management which is modeled as an alliance model.
Alliance model is based on information sharing and collaboration of several persons. The users disclose their taskcondition and maintain to be updatable by their friends. To avoid privacy issues we propose emergent group discovery
algorithm to control the level of disclosure. We implement client/server system on cellphones environment. We remark
the advantages of our approach with experimental evaluations.
KEYWORDS
collaborative scheduling, social network, cellphone application

1. INTRODUCTION
Progress of information society produces a large number of people who belong several communities. It
makes changes in the relationships between individuals and organizations. There are many non-profit andnon-governmental organizations as well as conventional organizations such as enterprises and schools but
also increasing. People participate multiple groups properly to fit variety of their life.
To improve the quality of life, it is necessary to manage personal resources e.g., time, asset andknowledge. There are many studies and systems on resource coordination to support resource
management[klusch01]. They can be divided into two categories, one is a top-down model and the other isbottom-up model.
A typical case of top-down model is groupware systems. Groupware enables information sharing andresource reservation among an organization to enhance its productivity. The system can also manage
constituents' resources with hierarchical authority.
However these conventional methods are not appropriate for people described above, since most of thesesystems are designed for single organization. It is also exceedingly difficult to work with multiple groupware
due to their inconsistent data structures and security problems[wellman01]
On the other hand, popular personal management methods, which consist of day planners, calendars,
Personal Information Manager (PIM) software and Personal Digital Assistant (PDA) devices, contribute tosimple management of personal information. But they do not guarantee efficient time control in multiple
groups because of their arbitrariness. To resolve this problem, Ohmukai et al. proposed and evaluated apersonal task scheduler based on decision-making theory[ohmukai03]. However this method cannot decrease
the cost of information input which is a common problem in bottom-up models.

In this paper we propose a collaborative approach for personal task management which takes a middle
position between groupware models and personal models. We also develop a cellphone-based schedulingsystem with the idea and investigate the performance of the system with an experiment.
This paper organizes as follows. In section 2 we describe "Information and Communication Activities" asa basic concept of collaborative approach. In section 3 we review the objective problem and propose thecollaborative model of resource management with ICA concept. In section 4 we explain an information
filtering method based on social networks. In section 5 we describe the specification of the implemented
system called Social Scheduler. We examine the performance of our system in section 6, then we summarize
the paper in the last section.

2. INFORMATION AND COMMUNICATION ACTIVITIES
2.1 From ICT to ICA
Computers and networks enrich and facilitate our life so that they now become indispensable for our life.
They sometimes enhance our traditional daily activities with their increasing computing and networking
power like documenting and communicating with other people, and sometime offer new ways for ouractivities with new technologies like WWW.
On the other hand, most people become to live with worry that unceasing improvement of computers andnetworks and installation of new software technologies would change their life and business.
It is not because of such technologies themselves but because of our vision to technologies. We are soeager to develop new technologies that we almost loose the original mission for development of technologies,
i.e., technologies just for us. Shneiderman pointed out that we should shift our vision from "old computing"to "new computing". He explained it in his recent book as follows[shneiderman02]; "The old computing wasabout what computers could do; the new computing is about what users can do. Successful technologies arethose that are in harmony with users' needs. They must support relationships and activities that enrich theusers' experiences."
We should shift our focus from information and communication technologies (ICT) to information andcommunication activities (ICA). We should investigate what are human activities on information andcommunication and how we can assist people in these activities.

2.2 Information and Communication Activities
Human activities on information such as collecting information and communication such as contacting topeople are only a part of human activities but they become to play an important role more and more inmodern life.
They include various kinds of activities. Shneiderman shows a simple and therefore understandable
model called ART (Activities and Relationships Table) for them. One axis of the table is activity category,i.e., Collect (information), Relate (Communication), Create (Innovation), and Donate (Dissemination). The
other is category of relationship, i.e., Self, Family and friends, Colleagues and neighbors, and Citizens andmarkets. We agree with relationship categories, while we think that activity categories should be elaborated
more because information handling and communication among people are mixed.
To explicate the difference, we propose two-layered model as an extension of his model shown in Fig. 1.
The first layer has three elements that concern information handling, i.e.,Collect (information)
Create (information)
andDonate (information).
It shows user-centered view of life cycle of information. Information is collected, then new information iscreated based on the collected information, and finally created information is donated to the society for futurecreation[lessig01]. It should be noted that new information is seldom created from scratch but created basedon existing information1.
The second layer has also three elements that concerns communication handling, i.e.,Relate (people)
Collaborate (with people)
andPresent (people).

Fig. 1 Information and Communication Activities}

It is communication-centered view of the above process. People establish relationship with other people,
then collaborate with them to create new information, and finally present themselves as donor of newinformation. Having both information and communication layers is not redundant. What we refer as"information" in the context of computer technologies is stored data in computers, while human is the sourceof "information" in the broader sense, i.e., human can offer information dynamically. We should consider
communication in order to include the function "human as information source". This parallel view of
information and communication activities has thus six categories as activities. Ideally all categories should be
supported by computers. Some categories like Collect is well investigated, but others are not. In particular,
the three categories in the communication layer should be investigated more.
We aim to investigate information and communication activities and support people in the all categoriesof the activities. We call such support "information and communication activity navigation (ICAN)". It helps
people to create new information by guiding information space and human network.

3. COLLABORATIVE TASK SCHEDULING
3.1 Summary of Personal Task Scheduling
Scheduling problems are modeled as the process that aligns the personal tasks with her/his time resource.
The basic constraint of this problem is that a single time resource cannot be reserved for multiple tasks. Manytechniques for resolving various types of scheduling problems were proposed such as optimization andconstraint solving methods[noronha91].

1We do not claim that information creation is just combination of existing information. Rather creativity arises with
understanding and interpretation of existing information.

However these methods cannot treat personal task scheduling problems since the tasks have variety intheir purpose and value and people have their own standards for managing the tasks.
In the research area of knowledge management and network community, several problem solving
methods based on information sharing are proposed[kamei01][klusch01], but it is exceedingly difficult towork with multiple people and groups because these methods are focused on the management in single
organization and community.

3.2 Concept of Trusty Information Sharing
Most of personal tasks come up as request for collaboration with people who are in the personal network.
Once you accept these tasks it is hard to change their deadline or the time of appointment. Especially the casethat several tasks from different groups require the same period, you should negotiate with one of the clientsand then with another client. It will complicate the problem and increase the cost of conflict resolution.
To avoid this situation it is desirable that people can make decision without any negotiations. We
proposed a simple solution based on "trusty information sharing". Fig. 2 shows the concept of our model.
This model can be divided into two parts, one is how to detect of trusty groups and people, and the otheris how to make decision or reservation in that trusty groups.

Fig. 2 Model of Trusty Information Sharing

Top-down approach including groupware already enables effective resource management and schedulingby sharing all task information of constituent members because these systems regard that all people must betrusty.
In a situation of inter-organization scheduling, however, it is unreasonable to disclose and share all
personal information because of a fear about violations of the users' privacy.
Therewith it is important to introduce a new method to detect trusty groups and people. Difficulty lies on
how to identify such trusty people. Most of conventional methods require the profiles which are described byusers so that the input cost will be extremely high.
We here propose a method based on social network analysis. This method consists of automaticconstruction of social network, personal group detection from the network and information filtering using thegroups. Our system always observes and analyzes the users' behavior and filters the personal information
with the result.
With this method we can identify trusty groups and people dynamically. Then people can disclose theirpersonal information appropriately and they can decide their own schedules easily.
Fig. 3 shows the model of our system.
Decision-making activities shown in the left side of Fig. 3 are performed by the users. An user who wants
to request a task to other confirms the friends' task condition in advance and then she/he reserves theirresource with consideration not to be overbooking. If the users accept a collaborative task, the system extendssocial network. The system detects trusty groups and people with three functions shown in the right side ofFig. 2. When a user collect friends' schedule information, the system selects their information not to disclose
unnecessary data. These processes will make the formation of loop as a result.

Fig. 3 Model of Social Network Analysis

4. TRUSTY INFORMATION SHARING BASED ON SOCIAL NETWORKANALYSIS
Our model provides democratic and collaborative scheduling method. We introduce the personal network
for collaboration and the alliance network in order to realize our smart filtering method.
A personal network contains the authorized relations and the collaborative relations with other users. Theauthorized relations shown in the left side of Fig. 4 are generated from requests for communication, and thecollaborative relations are constructed from requests for performing the same task together. All of personal
networks are merged into the alliance network by the server. Smart filtering method can find a suitable levelof disclosure of personal information by identifying emergent groups from the alliance network. The server
regards complete graphs in the alliance network as emergent groups, and assumes these groups as units ofinformation sharing.

Fig. 4 Collaborative ModelThe users can generate collaborative tasks with the other users on their personal network. Server reposits
task information on the collaborative task database, and renews their repositories on the task-based relations
called collaborative relations as shown in the right side of Fig. 4.

The server decides whether the user can access the task data of other users as follows. First the server
receives IDs of the user and the authorized user (friend) and sends the task data of friends which she/he sets
up as available for access. To control tasks smartly the server constructs collaboration matrix fromcollaborative task database. The server applies complete graph discovery algorithm to the matrix andacquires the name list of groups including both the user and friends. Finally the server compares the list with
the names of tasks of friends and sends tasks of which former comprises latter and denies cross-groupaccesses.
People can browse tasks and time conditions of other people if they are authenticated. The collaborativetask view shown in Fig. 5 displays simplified chronogram with her/his condition and two friends'. This
information is controlled by smart filtering method described above. In this example since there is a common
vacant periods, it is possible to perform a collaborative task together in such periods without negotiation. The
result will be displayed as the calendar view shown in the left of Fig. 6.
Our method enables the user to control personal information in cross-group environment without making
any profiles such as a member list of group.
Furthermore the user can select the level of information disclosure to each task from "deny from all", "usesmart filtering" and "allow from all".

Fig. 5 Collaborative Task View

Fig. 6 Calendar View (left) and Task Data View (right)

5. IMPLEMENTATION FOR CELLPHONE APPLICATION
We developed a prototype system based on server/client architecture.
Cellphone SO504i by NTT DoCoMo and Sony is used as the client. It is able to connect to the internet
and execute applications described with Java 2 Platform Micro Edition Connected Limited Device
Configuration (J2ME CLDC) by Sun Microsystems and J2ME Wireless SDK for DoJa. This device has 128
pixel by 128 pixel LCD display.
Debian/GNU Linux 3.0 with a self-made PC, Java 2 Platform Enterprise Edition (J2EE) 1.2, Java 2Standard Edition Runtime Environment (J2SE JRE) 1.4.1 and Tomcat servlet container 4.0 are used as theserver.

6. EXPERIMENTAL EVALUATION
6.1 Effects of the Alliance Model
We performed an experiment to confirm the effect of the alliance model. Nine persons participated andused our system practically for 3 weeks. These subjects belong to multiple organizations e.g., 3 persons
belong to A laboratory, 2 persons to B laboratory, 5 persons to C laboratory, 3 persons had belonged to Claboratory, 6 persons to D university, 4 persons had belonged to D university. Besides these relations there
are many relationships with friends among the subjects.
The average of the number of personal tasks input per person is 73.3. And total number of collaborative
tasks is 62. These tasks are concerned with 3.0 persons on average and make up 28.3% of personal tasks. The
alliance model has saved the users the cost of input 13.9 tasks on average.
From questionnaire survey, 8 persons of subjects replied that the number of tasks input in our system wasmore than in conventional tools they had used because other user entered collaborative tasks.
Therefore the alliance model fulfills its function.

6.2 Evaluation of Group Detection
Fig. 7 shows a social network as a result of the experiment. We obtain several emergent groups shown as
ovals in Fig. 7(a) by applying the group detection algorithm described before. Fig. 7(b) shows an user-centric
view of emergent groups. These results indicate that most of subjects belonged multiple groups andorganizations. To investigate the validity of our method, we ask the subjects to evaluate whether she/hesatisfied these emergent groups or not.

Fig. 7 Social Network

The total number of emergent groups exhibited to subjects is 24 and valid reply is 21. They answered that20 groups (95.2%) were discovered correctly. The subject pointed out that the rest was deficient in one
people. Moreover one of the subjects told that there was an undiscovered small group which was included bya large one. Our method cannot resolve this case so that it is necessary to apply more intelligent algorithms
such as clustering with frequency of task relations.

On the other hand, 1 group that was outguessed at the time of preparation was discovered with ourmethod. Because all people in the group satisfied with that fact, we can conclude that group detection method
worked well.

6.3 Evaluation of Smart Filtering
To verify our information filtering method, we present all task information with a list that who canbrowse the task to each subject. We also ask them to evaluate the result with "agree" or "disagree", and toannotate remarks from "1. wanted to deny from all", "2. wanted to allow only part of the list", "3. should nothave to restrict", "4. wanted to allow the rest of the list" and "5. wanted to allow from all". The first questionis indispensable and the second remarks are not necessary if she/he answers "agree" in first question.
The total number of the task is 660 and valid reply is 604. Table 1 shows the result of this evaluation.
Responses to the first question consist of 484 (80.1%) "agree" tasks and 120 (19.9%) "disagree" tasks. 15.9%of total and 80.0% of "disagree" mention those reason as "1. wanted to deny from all". In our system the user
can select the disclosure level of task to "deny from all" described in the previous section so that it is possible
to resolve this kind of the problem manually. Likewise 13 tasks with "3. should not have to restrict" (2.1% oftotal and 10.8% of "disagree") can be dissolved by setting to "allow from all". However 11 tasks with "2.
wanted to allow only part of the list" (1.8% of total and 9.2% of "disagree"), that is, overfull of information
disclosure cannot be clear with our current method. It is an issue to be solved in the future.

Table 1 Evaluation of Information Filtering

Hereby the number of "agree" tasks and "disagree" but easy-to-resolve tasks is 593 and 98.18¥% of total.
Scheduling support with our method was thus effective for this problem.

7. CONCLUSION
This paper proposes a collaborative approach for personal task management based on the alliance model.
The target of the proposed system does not contain hierarchical groups like corporate organization. In
these groups the total cost of decision-making can be reduced since superior people are able to control theschedules of subordinates. In flat communities, however, it is necessary to negotiate and compromise on
conflict of personal resource. Conflict resolution process will drive up costs remarkably thus most of profitmaking enterprises do not adopt such form of organization.
Our system premises that all the members of group should disclose her/his resource information. A user
can reserve resources of friends with a focus on her/his state. This feature will decrease unexpected collisionof tasks and cycles of negotiation. As a result the system provides cost reduction to keep flat organizations.

In this system it is not necessary to maintain the member list and select administrator of the group inadvance. The users only offer the collaborative task to their friends because the server performs detection ofboth human relationship and group identification automatically. This feature enables to support the bottomup and ad hoc groups appropriately
Social Scheduler system does not work well without self-directed disclosure of each user. Fear ofoverloaded disclosure of personal data and invasion of privacy may interfere with popularizing the system.
Our smart filtering method can resolve these problems by identifying the emerging groups and prohibiting
cross-group query. This method brings the users benefit of information sharing with a minimum of demerit
mentioned above.
Our system provides that a member updates the task databases of multiple follow members directly. Thus
the total costs of data input are decreased because their friends do not have to enter the collaborative tasks inher/his own repositories.
A further direction of this study is to sophisticate our system and to expand the scope of personal
resources. We are planning to perform an experiment with large-scale groups. In addition to the experiment
we will investigate nature of personal tasks.

REFERENCES
Klusch, M., 2001. Information Agent Technology for the Internet: A survey. Data and Knowledge Engineering, Vol. 36.
Wellman, B., 2001. Computer Networks As Social Networks. Science, Vol. 293, pp. 2031-2034.
Ohmukai, I., Takeda, H., and Miki, M., 2003. A Proposal of the Person-centered Approach for Personal Task
Management Proceedings of 2003 Symposium on Applications and the Internet (SAINT2003), pp. 234-240.
Shneiderman, B., 2002. Leonardo’s Laptop: Human Needs and the New Computing Technologies. MIT Press.
Lessig, L., 2001. The Future of Ideas: The Fate of the Commons in a Connected World. Random House.
Klusch, M., 2001. Information Agent Technology for the Internet: A survey. Data and Knowledge Engineering, Vol. 36.
Noronha, S. J. and Sarma, V. V. S., 1991. Knowledge-Based Approaches for Scheduling Problems: A Survey. IEEE
Transactions on Knowledge and Data Engineering, Vol. 3, No. 2, pp. 160-171.
Kamei, K. et al. 2001. Community Organizer: Supporting the Formation of Network Communities through Spatial
Representation. Proceedings of 2001 Symposium on Applications and the Internet (SAINT2001).